第7回　文字列の中から効率良くキーワードを探し出せ

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

2009/2/4

KMP法

- PR -

　力任せ法以外の方法は、普通にはなかなか思い付きません。しかし、より効率の良い方法がいくつもあります。

　文字列探索は、文字列の中の1文字と検索ワードの中の1文字にそれぞれ着目して比較することを繰り返します。ここで、着目している位置を指し示すものをポインタと呼ぶこととします。具体的には、何文字目かを表す数値の変数をイメージしてください。このポインタの進め方を工夫することで効率を良くすることができます。

　例えば、以下の例を考えてみましょう。

文字列：abababbbabc
検索ワード：ababc

　力任せ法の場合を考えます。左から順に1文字ずつ比較すると「abab」まで一致しています。次の文字は、文字列では「a」、検索ワードでは「c」となり不一致です。そこで、文字列のポインタを1つ進めて2文字目の「b」、検索ワードの先頭「a」から比較を始めます。

　5文字目まで進んだ文字列側のポインタが、2文字目まで戻りました。これは実に無駄です。

　「abab」まで一致していることが確かめられています。ということは3、4文字目の「ab」は、検索ワードの先頭の2文字「ab」と一致しており、文字列の5文字目と検索ワードの3文字目から比較を継続してもよいはずです。

　このように検索ワードのどの位置で不一致になったかを把握することによって、どこから比較を再開すればよいかをあらかじめ決めることができます。文字列側のポインタを戻さなくて済みます。

　この文字列探索アルゴリズムがKMP法です。KMPとは、このアルゴリズムを考えた人たち（Knuth-Morris-Pratt）の頭文字です。

KMP法の比較再開テーブル

　では、どこから比較を再開するかを、どのようにして考えればよいでしょうか。先ほどの例で考えてみましょう。 文章だけでは分かりにくいので、ぜひ上のような図を書いてポインタの動きを追ってみてください。

　まず、1文字目の「a」で不一致になった場合。この場合は文字列のポインタを1つ進め、検索ワードのポインタは先頭にすればよいでしょう。

　2文字目の「b」で不一致になった場合。文字列のポインタはそのままに、検索ワードのポインタを先頭に戻せばよいでしょう。

　3文字目の「a」で不一致になった場合。先頭から再度比較するとしても、先頭も「a」なので必ず不一致になります。従って、文字列のポインタを1つ進め、検索ワードのポインタを先頭に戻します。

　4文字目の「b」で不一致になった場合。2文字目の「b」と同様に、文字列のポインタはそのままで、検索ワードのポインタを先頭に戻します。

　5文字目の「c」で不一致になった場合。先ほど見たように直前2文字の「ab」が一致するので、文字列のポインタはそのままに、検索ワードのポインタを3文字目にすればよいでしょう。

　 このように、どこから比較を再開するかは、 検索ワードの中に、検索ワードの先頭と同じ文字の並びがあるかどうかで決めることができます。 5文字目の場合がもっとも分かりやすいでしょう。

　従って、比較再開テーブルは、検索ワード同士を比較して計算します。

KMP法の実装

　では、KMP法を実装しましょう。先ほどのプログラムの末尾にある「末尾1」というコメントに続けて、以下のプログラムを追加してください。

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
<script type="text/javascript">
String.prototype.getKMPNext = function() {
  var next = new Array();

  next[0] = -1;
  var n = next[0];
  for (var i = 0; i < this.length; i++) {
    while (n > -1) {
      if (this.charAt(i) == this.charAt(n)) { break; }
      n = next[n];
    }
    n++;
    var j = i+1;
    if (this.charAt(j) == this.charAt(n)) {
      next[j] = next[n];
    } else {
      next[j] = n;
    }
  }

  return next;
}

String.prototype.findKMP = function(str) {
  var next = str.getKMPNext();

  var text_idx_len = this.length - str.length + 1;
  var n = 0;
  for(var text_idx = 0; text_idx < text_idx_len; text_idx++) {
    while (n > -1) {
      if (this.charAt(text_idx) == str.charAt(n)) { break; }
      n = next[n];
    }
    n++;
    if(str.length <= n) {
      return text_idx - str.length + 1;
    }
  }
  return null;
}

function findTextAreaKMP(text_id, search_id) {
  var text = getStringById(text_id);
  var search = getStringById(search_id);
  alert(text.findKMP(search));
}
</script>
<input type="button" onClick="findTextAreaKMP('area1','search');" value="findKMP">
<!-- 末尾2 -->

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

2〜22行目

比較再開テーブルを作成する関数です。

配列nextが、検索ワードの何文字目で不一致になったときに、何文字目から比較再開するかを保持します。例えば、2文字目で不一致だった場合は、next[1]に比較再開する文字の位置が入っています。next[i]=0だったら先頭になります。next[i]=-1だった場合は、文字列側のポインタを1つ進めて、検索ワード側のポインタを0にするという意味になります。

24〜40行目

KMP法で探索する関数です。

25行目

比較再開テーブルを計算します。

28行目

nが検索ワード側のポインタです。

29行目

text_idxが文字列側のポインタです。

30〜33行目

文字列の1文字と検索ワードの1文字を比較します。

一致するとnとtext_idxが両方1進みます。不一致になると比較再開テーブルを参照して、再度文字列と検索ワードの1文字を比較します。

比較再開テーブルに-1が入っていたらwhileループを抜けます。

35〜37行目

nが検索ワードの文字数まで進んだ＝全部一致したということで、一致した文字の位置を返します。

2/4

Index
文字列の中から効率良くキーワードを探し出せ
  Page1
力任せ法
Page2
KMP法
KMP法の比較再開テーブル
KMP法の実装
  Page3
BM法
BM法の実装
  Page4
N-gram Index
N-gram Indexの実装

コーディングに役立つ！ アルゴリズムの基本
　Coding Edgeお勧め記事
いまさらアルゴリズムを学ぶ意味
コーディングに役立つ！ アルゴリズムの基本（1）　コンピュータに「3の倍数と3の付く数字」を判断させるにはどうしたらいいか。発想力を鍛えよう
Zope 3の魅力に迫る
Zope 3とは何ぞや？（1）　Pythonで書かれたWebアプリケーションフレームワーク「Zope 3」。ほかのソフトウェアとは一体何が違っているのか？
貧弱環境プログラミングのススメ
柴田 淳のコーディング天国　高性能なIT機器に囲まれた環境でコンピュータの動作原理に触れることは可能だろうか。貧弱なPC上にビットマップの直線をどうやって引く？
Haskellプログラミングの楽しみ方
のんびりHaskell（1）　関数型言語に分類されるHaskell。C言語などの手続き型言語とまったく異なるプログラミングの世界に踏み出してみよう
ちょっと変わったLisp入門
Gaucheでメタプログラミング（1）　Lispの一種であるScheme。いくつかある処理系の中でも気軽にスクリプトを書けるGaucheでLispの世界を体験してみよう
　　Coding Edgeフォーラムフィード　 2.0／1.0／0.91

TechTargetジャパン

Coding Edge フォーラム 新着記事

＠ITメールマガジン　新着情報やスタッフのコラムがメールで届きます（無料）

RSSフィード

＠IT 新着記事

キャリアアップ

＠IT Sepcial
→ ＠IT Special ヘ

イベントカレンダー

PickUpイベント

- PR -
もっと見る

お勧め求人情報

ホワイトペーパー（TechTargetジャパン）

＠IT Sepcial
→ ＠IT Special ヘ
ソリューションFLASH