文書から機械的にキーワードを切り出す方法 ~文字N-gram方式~
発想を思い切って転換してみましょう。転置インデックスのために切り出すキーワードは、巻末索引と違って人間の目に触れることはありません。それならば、キーワードの切り出しアルゴリズムは人間の都合を無視してパソコンの都合だけで決めてしまってもかまわないのではないのでしょうか。切り出されたキーワードは人間にとって意味のない文字列であってもかまわない、と割り切るわけです。「え~、人間の都合を無視してしまって本当に大丈夫なの? 不安だなぁ」―――はい、その気持ちはよくわかります。その不安を解消する方法については後の回で扱いますので、ここはその不安はいったん脇において先に進みましょう。
下の図を見てください。
「自然言語処理は面白い。」という文から、「自然」「然言」「言語」「語処」「処理」「理は」「は面」「面白」「白い」「い。」という11個の「キーワード」が切り出されています。ここで適用した「キーワード切り出しアルゴリズム」は、「文書を構成する文字列から、長さ2のすべての部分文字列を取り出す方法」というものです。このアルゴリズムを「アルゴリズムX」と呼ぶことにしましょう。はたしてアルゴリズムXを用いた文書検索システムが先に挙げた3つの条件を満たしているか、検証してみましょう。
1.キーワードの切り出しについての明確な手順が与えられていること
「アルゴリズムX」は、極めて単純で明確なプログラムによって実現できます。誰がプログラムを書いても同じようなものができるでしょう(参考までに、Javaというプログラミング言語で書いたプログラムリストと、その実行結果を下に示します)。よって、この条件は満たしています。
import java.util.ArrayList;
/**
* アルゴリズムXのサンプルコード
*
* @author kiyota
*
*/
public class AlgorithmX {
/**
* 切り出す「キーワード」の長さ
*/
static final int KEYWORD_LENGTH = 2;
/**
* 任意の文字列から「キーワード」を切り出す
*
* @param sentence
* 任意の文字列
* @return キーワードの配列
*/
public ArrayList<String> getKeywords(String sentence) {
// 切り出し結果を格納する配列
ArrayList<String> keywords = new ArrayList<String>();
// 文字列が空の場合のチェック
if (sentence == null) {
return keywords;
}
// 文字列の先頭から開始場所を1文字づつずらしながら、
// 「KEYWORD_LENGTH文字」だけ切り出していく
for (int i = 0; i <= sentence.length() - KEYWORD_LENGTH; i++) {
keywords.add(sentence.substring(i, i + KEYWORD_LENGTH));
}
return keywords;
}
/**
* @param args
* 引数に任意の文字列を入力してください。
* 実行例: java AlgorithmX 自然言語処理は面白い。
*/
public static void main(String[] args) {
if (args.length == 1) {
AlgorithmX algorithmX = new AlgorithmX();
ArrayList<String> keywords = algorithmX.getKeywords(args[0]);
for (String keyword : keywords) {
System.out.println(keyword);
}
} else {
System.err.println("引数として1個の文字列を与えて実行してください。");
}
}
}
2.文書と検索要求の両方に同じキーワード切り出しのアルゴリズムが適用できること
「アルゴリズムX」は、文書だけでなく検索要求にも適用できます。たとえば、「自然言語処理は」という検索要求から、「自然」「然言」「言語」「語処」「処理」「理は」という6個の「キーワード」が切り出せます。よってこの条件も満たしています。
3.アルゴリズムによって切り出された文字列が「検索の手掛かり」として使えること
「自然」「言語」「処理」という文字列が「検索の手掛かり」となるのは何となく想像がつくことでしょう。問題は「然言」「語処」といったちょっと変な文字列ですが、これらも検索にとっては有力な手掛かりです。なぜなら、「自然」「然言」「言語」「語処」「処理」という5つの「キーワード」が存在するということは、「自然言語処理」という言葉が使われている、ひとつの有力な根拠として使えるからです(後の回で詳しく述べますが、必ずしも確実な証拠ではありません)。よってこの条件も満たしています。
いかがでしょうか? 人間の目から見ればとても「キーワード」とは呼べなさそうな文字列を切り出してくる「アルゴリズムX」が、文書検索システムで使えるものであることが証明できてしまいました。
実は、「アルゴリズムX」は実用的な文書検索システムでも採用されている人気のあるアルゴリズムなのです。このアルゴリズムのことを、一般には文字N-gram(エヌグラム)方式と呼んでいます。より正確には、文字N-gram方式は「文書を構成する文字列から、長さNのすべての部分文字列を取り出す方法(ただしNは正の整数)」と表現できます。アルゴリズムXはN=2、つまり文字2-gram方式です。ちなみに、「1-gram」は「ユニグラム(uni-gram)」、「2-gram」は「バイグラム(bi-gram)」、「3-gram」は「トライグラム(tri-gram)」と読みます。
文字N-gram方式を使うことで、前回の最後に挙げた1枚目の壁「文書の文字列からどうやってキーワードを切り出すのか?」を乗り越えられることが理解できたでしょうか。パソコンの動く仕組みを考える場合、時には「人間の都合を無視して、パソコンの都合だけを考える」ことも必要になります。もし本連載を読み進めていく上で詰まってしまうところがあったら、「人間の都合を離れてパソコンの気持ちになって考えてみる」ことを心がけてみましょう。
次は、2枚目の壁「キーワードの列からどうやってお目当てのキーワードをすばやく探し出すのか?」を乗り越える方法を2通り紹介していきます。