JavaScriptで全文検索(N-gram)を実装してみる！

プラコレアドベントカレンダーもラストスパート！こんにちは、森です！

仕組みをちゃんと理解するには実装してみることが一番！ということで、N-gramの中でも一番実装が簡単なuni-gramをjsで実装してみました！

全文検索とは
uni-gram
インデックスの作成
1. 文章にdocument IDを振る
2. 文字列の分割
3. 文字位置付与
4. トークンごとに位置情報をまとめる
5. トークンをキーに引けるように保存
インデックスから検索
1. 検索文字列をトークンに分割
2. インデックスからトークンのデータを取得
3. 取得したデータをつなぎ合わせる
実装
動かし方
インデックスの作成
インデックスから文字列を検索
コード
参考文献
最後に

全文検索とは

まず最初に全文検索とはなにかってことですが、Wikipediaで調べてみました「コンピュータにおいて、複数の文書（ファイル）から特定の文字列を検索すること。「ファイル名検索」や「単一ファイル内の文字列検索」と異なり、「複数文書にまたがって、文書に含まれる全文を対象とした検索」という意味で使用される。」とあります。要するに複数のテキストファイル(文章)から特定の単語が見つけられれば良いってことですね。

ただ、grepを使ってすべてのファイルを頭から検索していっても良いのですが、それだと検索のたびに全文字列にアクセスと比較が発生してしまって文章ファイルが増えれば増えるほどどんどん遅くなっていってしまいます。

なので、全文検索のシステムでは最小限のアクセスで検索したい単語が入っている文章を見つけるための工夫がされています。

主にどういう方法をとっているかというと、本の索引のように単語がどこにあるかという情報を作成して検索を行っています。

uni-gram

索引を作るにあたって、文章をトークンという単位に分割する必要があります。日本語をトークンに分割する方法で良く使われるものに、形態素解析とN-gramというものがあります。今回は実装が一番簡単なuni-gramを使って実装しました。

形態素解析

形態素解析では文法規則に則って文章を分割する方法です。N-gramと比べたときの利点と欠点については以下のものが考えられます（検索ノイズというのは「東京都」が登録されたときに「京都」で検索して引っかかってしまったりすること）

利点：検索ノイズ（検索に一致してほしくない単語が引っかかってしまう）が減る

欠点：JUMAN++やMeCabやkuromojiといった文法規則に則って分割するためのソフトウェアが必要

明日はクリスマスをトークンに分割するとこのようになります。

| 明日 | は | クリスマス |

N-gram

N-gramとは、uni-gram(1-gram)、bi-gram(2-gram)、tri-gram(3-gram)・・・というようにNの数ずつ一つずつずらしてトークンを分割していきます。

uni-gramの場合は

明 | 日 | は | ク | リ | ス | マ | ス

bi-gramの場合は

明日 | 日は | はク | クリ | リス | スマ | マス

tri-gramの場合は

明日は | 日はク | はクリ | クリス | リスマ | スマス

というように分割します。

形態素解析と比べたときの利点と欠点については以下のようなものがあります。

利点：分割方法が単純で形態素解析のようなものが必要ない

欠点：すべての文字が検索に引っかかる（検索ノイズが多い）

また、Nが増えたときの利点と欠点については（この利点と欠点については明確にどこかに書かれていた訳ではないので違っていたら教えてもらえると嬉しいです！）

利点：トークンに対するドキュメントの情報とトークンの位置情報が減るので、データの読み出しや、トークン同士がつながっているかの確認処理が速くなる（例えばuni-gramで「は」のトークンは文章中に大量に存在するのでトークンに対する情報が多くなるが、bi-gramの「日は」や「はク」はそこまで登場回数は多くならない）

欠点：N未満の文字数の単語には引っかからない

インデックスの作成

今回uni-gramを使って「今日はクリスマス・イブ」「明日はクリスマス」という文章があった場合を例にとってインデックスを作成してみます。

1. 文章にdocument IDを振る

まず文章を識別するためにdocument IDを振ります。

document ID	文章
0	今日はクリスマス・イブ
1	明日はクリスマス

2. 文字列の分割

今回uni-gramを使用するので↓の様に一文字ずつ分割します。分割した文字をトークンと呼びます。

document ID 0

今 | 日 | は | ク | リ | ス | マ | ス | ・ | イ | ブ

document ID 1

明 | 日 | は | ク | リ | ス | マ | ス

3. 文字位置付与

先頭からのトークンの位置をドキュメントごとに調べます。位置は0から始めています。

document ID 0

トークン	位置
今	0
日	1
は	2
ク	3
リ	4
ス	5
マ	6
ス	7
・	8
イ	9
ブ	10

document ID 1

トークン	位置
明	0
日	1
は	2
ク	3
リ	4
ス	5
マ	6
ス	7

4. トークンごとに位置情報をまとめる

同じトークンの場合は位置情報をまとめます（スが被っているのでまとめています）

document ID 0

トークン	位置
今	0
日	1
は	2
ク	3
リ	4
ス	5,7
マ	6
・	8
イ	9
ブ	10

document ID 1

トークン	位置
明	0
日	1
は	2
ク	3
リ	4
ス	5,7
マ	6

5. トークンをキーに引けるように保存

トークンをキーにして保存（今回はファイル名をトークンにして保存します）

Key-Valueストアのようにキーでコスト低く引けるようにしておきます。

document IDと位置情報をコロンで区切り、位置情報が複数ある場合はカンマで区切ります。そして、文章が複数ある場合は以下のように改行で区切って表すことにします。

<document ID>:<位置>,<位置>\n<document ID>:<位置>,<位置>

key	value
今	0:0
日	0:1\n1:1
は	0:2\n1:2
ク	0:3\n1:3
リ	0:4\n1:4
ス	0:5,7\n1:5,7
マ	0:4\n1:4
・	0:8
イ	0:9
ブ	0:10

ここまででインデックスが作成できます！ちょっと長くなってしまいましたが、やっていることは文章をトークンに分けてトークンごとに文章と出現位置をまとめなおすということをやっています。

インデックスから検索

先程作成したインデックスから「クリスマス・イブ」という文字列を検索してみます。

1. 検索文字列をトークンに分割

ク | リ | ス | マ | ス | ・ | イ | ブ と一文字ずつ分割します。

2. インデックスからトークンのデータを取得

インデックスからトークンのデータを取得するとこのようになります。

ク => 0:3\n1:3

リ => 0:4\n1:4

ス => 0:5,7\n1:5,7

マ => 0:4\n1:4

ス => 0:5,7\n1:5,7

・ => 0:8

イ => 0:9

ブ => 0:10

3. 取得したデータをつなぎ合わせる

検索文字列の最初のトークンからdocument IDと位置を確認しながらつながっているかを確認していきます。

まず先程取得したデータから「ク」はdocument ID 0の3の位置、document ID 1の3の位置にあることが分かります。

次に「リ」を見るとdocument ID 0の4の位置、document ID 1の4の位置にあります。ここから、「ク」の位置に1を足した位置に「リ」があることからdocument ID 0と1両方ともつながっていることがわかります。

このまま「ス」も見てみます。document ID 0の5と7の位置、document ID 1の5と7の位置にあります。ここから、「リ」の位置4に1を足した5があることから「ス」と「リ」がつながっていることがわかります。

このように順番につなげていくとクリスマスまではつながると思います。もし途中で繋がらなかったらその単語は文章中に登場しないということになります。

続けて「・」も見てみるとdocument ID 0の情報しかないので、document ID 1には「クリスマス・イブ」がないことがわかります。

このように最後まで順番通りつながったら単語が見つかったということになります🎉

実装

動かし方

まず、完成品があるので動かし方を説明します。

コードをダウンロード
npm install readline-syncでreadline-syncをインストール
mkdir docs && mkdir tokensで文書ファイルを置くためのdocsディレクトリと、トークンデータを置くためのtokensディレクトリを作成
検索したい文章をdocsディレクトリ以下に置く
node createIndex.jsでインデックスファイルを作成
node searchFromIndex.jsでインデックスファイルから文字列を検索

インデックスの作成

インデックスの作成にはcreateIndex.jsとdocument.jsというファイルを使って実装しました。

document.js

ファイルのパスとインデックス作成時に使うdocumentIDを渡して、saveTokens(outputFileDir)を実行するとoutputFileDirにインデックスファイルが書き出されます。

トークンへの分割

トークンへの分割はtokenizer(text)という部分で文章からトークンの作成をしています。今回はuni-gramを使うので文字列を配列にしているだけです（カンタン♪）ただし、このとき4バイト以上のUTF8の文字の分割に対応するため、text.split('')ではなく、Array.from(text)を使用しています。

トークンごとの位置情報データ

tokenClassificationメソッドでトークンごとに位置情報データをまとめて以下のようなデータにしています。

{
  '途': [ 649, 1020, 1153 ],
  'ぶ': [ 651, 1051, 1220, 1222 ],
  '下': [ 653, 664, 667, 759, 885, 1053 ]
}

インデックスデータの保存

トークンをキーとしてkey-value形式で保存したいので、ファイル名にトークンを使います。この際ファイル名に/の様な使えない文字があるので、charCodeAtメソッドを使って文字を数字に変換してファイル名として使っています。

'あ'.charCodeAt(0) // 12354

ファイルの中身は以下の様な形式で保存しています。

<document ID>:<トークン位置>,<トークン位置>,・・・
<document ID>:<トークン位置>,<トークン位置>,・・・

0:1,5,7,120,135,358,397,425,436,489,510,590,689,690,699,712,732,742,752,757,761,771,774,777,782,791,810・・・
1:18,45,66,145,509,540,609,766,874,930,962,1104,1169,1202,1203,1345,1360,1369,1501,1543,1824,2419,2461・・・
2:5,36,102,177,206,252,318,435,484,490,595,734・・・

（プログラムでは処理を簡単にするためファイルの存在確認をせずappendFileSyncで追記を行っているので、ファイルの先頭に空行ができています）

createIndex.js

document.jsでは文章一つに対してインデックスファイルを作成しているので、これをdocsディレクトリ内にあるファイル全部に対して実行するようにしています。

あと、documentIDと文章のファイル名（タイトル）を紐付けるためのファイル(docs.json)も同時に作成しています。

{
  "0": {
    "name": "人間失格.txt",
    "path": "./docs/人間失格.txt"
  },
  "1": {
    "name": "吾輩は猫である.txt",
    "path": "./docs/吾輩は猫である.txt"
  },
  "2": {
    "name": "蜘蛛の糸.txt",
    "path": "./docs/蜘蛛の糸.txt"
  }
}

インデックスから文字列を検索

search.js

search.jsでは受け取った文字列がインデックス内にあるか検索します。

検索文字列からインデックスデータを取得

getTokenListメソッドで検索文字列を分割して、トークンそれぞれのファイルを取得します。取得したデータをtokenListParseメソッドに投げ、documentIdをキー、位置情報の配列を値とする連想配列とする以下のようなデータが返ってきます。

{
  "0": [1,10,15],
  "1": [8,9]
}

トークンごとのデータをつなぎ合わせる

tokenListParseメソッドで取得してきたデータが以下のようなデータになっていたとき

{
  "0": [1,10,15],
  "1": [8,9]
}

{
  "0": [2,11],
  "1": [9,23,51]
}

{
  "0": [9,12,71],
  "1": [77,91]
}

それぞれのdocumentIdごとにつながっているか確認していきます。documentIdが0のものを見ていくと、[1, 10, 15]に1を足した配列[2, 11, 16]と[2, 11]の積集合をとります。すると[2, 11]になるので、これに１を足して次の配列とまた積集合を取ります。

すると、[12]が最終的に出てきます。配列の値がある間は繋がっているということなのでその個数を数えておきます。

上記のことをやっているのがconnectTokensメソッドです。

繋がっていたトークンの個数のチェック

繋がっていたトークンの個数と検索の文字列を分割したトークンの個数が一致しているかを調べます。チェックして一致したらその文章内に検索文字列があるということなのでdocumentIdを返します。

見つかった文章を表示

見つかったdocumentIdがsearch.jsでは返却されるので、searchFromIndex.jsでは受け取ったdocumentIdを、インデックス作成時に保存したdocs.jsonから文章情報を引っ張ってきて表示して完了です！

コード

参考文献

高速文字列解析の世界

最後に

明日はどんな技術も貪欲にどんどん吸収している次世代エース沢岻くんです！Three.jsでクリスマスカード？想像できないですがとっても凄そう！楽しみにしています！！！

プラコレWeddingでは検索もElasticsearchを使って実装したりもしています！Elasticsearchを使ってみたいエンジニア、新しいことに挑戦したい人など、エンジニア、デザイナーも幅広く募集しています！！

プラコレではプラコレWedding以外にも花嫁メディアDressy（ドレシー）やfarny（ファーニー）なども運営しています。ぜひご覧いただけますと嬉しいです！

JavaScriptで全文検索(N-gram)を実装してみる！

目次

全文検索とは

uni-gram

形態素解析

N-gram

インデックスの作成

1. 文章にdocument IDを振る

2. 文字列の分割

3. 文字位置付与

4. トークンごとに位置情報をまとめる

5. トークンをキーに引けるように保存

インデックスから検索

1. 検索文字列をトークンに分割

2. インデックスからトークンのデータを取得

3. 取得したデータをつなぎ合わせる

実装

動かし方

インデックスの作成

document.js

createIndex.js

インデックスから文字列を検索

search.js

コード

参考文献

最後に

関連記事