文字列の中から効率良くキーワードを探し出せ：コーディングに役立つ！ アルゴリズムの基本（7）（4/4 ページ）

[山下寛人，オイシックス株式会社]

N-gram Index

　KMP法とBM法は、検索ワードの方に前処理をしました。文字列の方に前処理をすることも考えられそうです。文字列に前処理をするアルゴリズムの1つがN-gram Indexです。

　本の中で特定のキーワードを探すとき、皆さんはどうしますか。1ページ目から全部探していくのは大変です。これは力任せ法です。普通は索引を使うと思います。N-gram Indexは、まさに索引をアルゴリズムにしたものだとイメージするとよいでしょう。

　まず、最初に文字列の中のすべての文字について、文字ごとに出現位置を計算します。複数回出現する文字も多数あると思いますので、出現位置はリスト構造など複数保持できるようにします。

　例えば、「First Fly Filter File」なら以下のような索引ができます。

	文字	出現位置
	F	0、6、10、17
	i	1、11、18
	r	2、15
	s	3
	t	4、13
	空白	5、9、16
	l	7、12
	y	8
	e	14、19

　検索するときには、検索ワードの先頭の文字に対応する索引を調べます。その位置から1文字ずつ一致するかどうかを調べます。不一致だったら、次の索引の位置から再度調べます。すべて調べて不一致だったら検索失敗です。

　索引は1文字に限る必要はありません。複数文字で索引を作る方法も考えられます。例えば、2文字で先ほどの文字列の索引を作ると以下のようになります。

	文字	出現位置
	Fi	0、10、17
	ir	1
	st	2
	・・・	・・・

　3文字以上でも同様です。1文字の場合をUnigram、2文字の場合をBigram、3文字の場合をTrigramと呼びます。

　文字数が多くなれば多くなるほど、文字の組み合わせが増えるので、索引に必要なメモリ領域が増えていきます。その半面、検索するときには、索引の時点でより多くマッチするかどうか調べられるので、素早く検索できる可能性が高くなるでしょう。

N-gram Indexの実装

　では、N-gram Indexを実装しましょう。先ほどのプログラムの37行目「末尾3」というコメントの次行以降に下記のプログラムを追加してください。

<script type="text/javascript">
function getNGramHash(text, n) {
  var hash = [];
  for (var i = 0; i < text.length+1-n; i++) {
    var index = text.substring(i, i+n);
    if (hash[index] == undefined) { hash[index] = []; }
    hash[index].push(i);
  }
  return hash;
}
 
function UnigramIndex(text_id) {
  var n = 1;
  var text = getStringById(text_id);
  var index_hash = getNGramHash(text, n);
 
  this.find = function(str) {
    var index_str = str.substring(0,n);
    var index_item = index_hash[index_str];
    for (var i = 0; i < index_item.length; i++) {
      var index = index_item[i];
      var isFound = true;
      for(var j = 0; j < str.length; j++) {
        if(str.charAt(j) != text.charAt(index + j)) {
          isFound = false;
          break;
        }
      }
      if (isFound) { return index; }
    }
  }
}
 
var unigram_index_hash = [];
function getUnigramIndex(text_id) {
  return unigram_index_hash[text_id];
}
 
function setUnigramIndex(text_id) {
  unigram_index_hash[text_id] = new UnigramIndex(text_id);
}
 
window.onload = function() {
  setUnigramIndex('area1');
}
 
function findTextAreaUnigram(text_id, search_id) {
  var text = getStringById(text_id);
  var unigram_index = getUnigramIndex(text_id);
  var search = getStringById(search_id);
 
  alert(unigram_index.find(search));
}
</script>
<input type="button" onClick="findTextAreaUnigram('area1','search');" value="findUnigram">

　プログラムを解説します。

2〜10行目

インデックスを作成する関数です。引数nには、何文字でインデックスを作るかを指定します。

4行目

文字列の各文字についてループします。

5行目

文字列からn文字分取得します。

6、7行目

インデックスに文字の位置を格納します。複数値が入るよう、配列にしてpushで値を追加します。

12〜32行目

Unigram Indexのクラスです。特定の文字列1つについてUnigramIndexのインスタンスが1つできます。

text_idを指定してnewすると、インデックスを作成して検索する準備を行います。その後find関数で検索を実行します。

13行目

nはインデックスの文字数です。Unigramなのでn=1です。

14行目

文字列を取得します。

15行目

インデックスを作成します。

17〜31行目

検索する関数です。

18行目

検索ワードからn文字分取得します。

19行目

取得した部分文字列に対応するインデックスを取得します。配列になっています。

20行目

取得したインデックスそれぞれについてループします。

23行目

インデックスの位置から検索ワードと文字列が一致するか1文字ずつ調べます。

29行目

ここでisFoundがtrueのままだったら、全部一致したということでindexの値を返します。

34行目

UnigramIndexオブジェクトを格納する変数です。特定の文字列について、検索するたびにnewすると毎回インデックスを作成することになります。1度インデックスを作成したら、何度作成し直しても同じものになるので、UnigramIndexのインスタンスを保存しておいて使い回します。

35〜37行目

text_idに対応するUnigramIndexオブジェクトを取得する関数です。

39〜41行目

UnigramIndexのインスタンスを生成した保存する関数です。

43〜45行目

ページを表示したときに「area1」に対応するUnigramIndexインスタンスを生成します。

47〜53行目

ボタンを押したときに実行する関数です。

　流れが複雑になっていますが、まとめると次のようになります。

1. ページが表示される
2. window.onloadが実行される（43行目）
3. setUnigramIndex('area1')が呼ばれる（44行目）
4. new UnigramIndex()が実行される（40行目）
5. UnigramIndexのコンストラクタ内でgetNgramHash()が呼ばれる（15行目）
6. ボタンが押される
7. findTextAreaUnigramが呼ばれる（47行目）
8. getUnigramIndexが呼ばれる（49行目）
9. ページ表示時に生成したUnigramIndexインスタンスが返ってきます。
10. find関数が実行される（52行目→17行目）

　以上で文字列探索は終わりです。次回は圧縮アルゴリズムを紹介します。

著者紹介

山下 寛人

オイシックス株式会社

「次回」へ

「コーディングに役立つ！ アルゴリズムの基本」バックナンバー

• レコメンデーションとエディットグラフ
• データを加工して圧縮率を高めよう
• データ量を操る圧縮／展開を究めよう
• 文字列の中から効率良くキーワードを探し出せ
• Firebugで探索アルゴリズムを見ていこう
• Internet Explorerよりも速くソートできたよ
• Internet Explorerよりも速くソートできるかな
• 再帰でハノイの塔を攻略せよ
• データ構造の選択次第で天国と地獄の差
• いまさらアルゴリズムを学ぶ意味