3.
実装方法
具体的にデータベースに実装する方法を説明します。
ここでは、SQL Server を対象としますが、要件を満たせれば、どのデータベース製品でもかまいません。
3.1. 検索対象のテーブル
検索対象のテキストを含むテーブルを次のようなものであるとします。
テーブル：SampleData
| 列名 |
データ型 |
| ID |
int |
| SENTENCE |
ntext |
IDは、レコードを特定するユニークな数値です。
このテーブルの SENTENCE列に、任意の文字列パターンを含むレコードの検索を目的とします。
このテーブルにレコードを追加する際には、次に説明するインデックスのテーブルにも必要なレコードを追加することになります。
3.2. インデックスのテーブル
N-Gramのインデックスとして使用するテーブルは次のような形式です。
テーブル：NGramIndex
| 列名 |
データ型 |
| CHARCODE |
nchar(N) |
| ID |
int |
| POSITION |
smallint |
- CHARCODE列は、固定長文字列で、N文字に区切った文字列を格納します。
- ID列には、検索対象のID値を格納します。
- POSITION列には、出現位置を格納します。
- ３つの列を主キーに設定します。
インデックスのサイズを小さくする為、POSITION列を smallint としていますが、SENTENCE列の文字数が smallint で表せる長さよりも大きい場合には、int にしてください。
ここで重要なのは、３つの列を主キーにする事です。
3.3. データの追加
例として、“天気予報によれば雨です”というテキストを追加します。
検索対象テーブルへの追加
検索対象のテーブルには、通常のレコードを追加する要領で行います。
INSERT INTO [SampleData] (SENTENCE) VALUES('天気予報によれば雨です');
ID列はIDENTITYの指定があり、自動的に番号が割り当てられるものとします。この値は、SCOPE_IDENTITY()等を使用して、取得するようにしてください。
ID値の割り当ては、どのような方法でもかまいません。
インデックスへの追加
インデックスを追加するには、次の SQL を実行します。
N を 4、ID は、検索対象のレコードのID値で123であるとします。
INSERT INTO [NGramIndex] ([CHARCODE],[ID],[POSITION])
VALUES ('天気予報',123,0);
INSERT INTO [NGramIndex] ([CHARCODE],[ID],[POSITION])
VALUES ('気予報に',123,1);
INSERT INTO [NGramIndex] ([CHARCODE],[ID],[POSITION])
VALUES ('予報によ',123,2);
INSERT INTO [NGramIndex] ([CHARCODE],[ID],[POSITION])
VALUES ('報によれ',123,3);
INSERT INTO [NGramIndex] ([CHARCODE],[ID],[POSITION])
VALUES ('によれば',123,4);
INSERT INTO [NGramIndex] ([CHARCODE],[ID],[POSITION])
VALUES ('よれば雨',123,5);
INSERT INTO [NGramIndex] ([CHARCODE],[ID],[POSITION])
VALUES ('れば雨で',123,6);
INSERT INTO [NGramIndex] ([CHARCODE],[ID],[POSITION])
VALUES ('ば雨です',123,7);
INSERT INTO [NGramIndex] ([CHARCODE],[ID],[POSITION])
VALUES ('雨です ',123,8);
INSERT INTO [NGramIndex] ([CHARCODE],[ID],[POSITION])
VALUES ('です ',123,9);
INSERT INTO [NGramIndex] ([CHARCODE],[ID],[POSITION])
VALUES ('す ',123,10);
最後の３つの INSERT 文では、文字数が不足しています。この SQL では空白が入ってしまいますが、実際には、システムとして取り決めた不可視の文字コードを入れます。
3.4. 検索
検索のSQLは少し複雑で、検索する文字列パターンの長さによって、異なるSELECT文を使用しなければなりません。
まず、検索対象のテーブルに対してのSELECT文があるものとします。
SELECT * FROM [SampleData]
これに、WHERE句を加えます。
SELECT * FROM [SampleData] WHERE ID IN (...)
この文のIN(...)の中に、検索結果のIDリストをサブクエリとして記述します。
以降は、このサブクエリ部分について説明します。
※ IN、サブクエリではなく、JOINを使用してもかまいません。
検索パターンがN文字の場合
検索する文字列パターンの長さが、インデックスの文字数 N と一致する場合です。
この場合の SELECT 文は非常に簡単で、N が 4 で“天気予報”を検索する SQL は以下のとおりです。
SELECT DISTINCT [ID]
FROM [NGramIndex] AS [idx_table0]
WHERE [idx_table0].[CHARCODE]='天気予報'
全体としては、次のような SQL です。
SELECT *
FROM [SampleData]
WHERE [ID] IN(
SELECT DISTINCT [ID]
FROM [NGramIndex] AS [idx_table0]
WHERE [idx_table0].[CHARCODE]='天気予報');
検索パターンがN文字未満
検索する文字列パターンの長さが N 文字未満の場合には、LIKE演算子を使用します。
インデックスの文字数 N が 4 で“予報”を検索するSQLです。
SELECT DISTINCT [ID]
FROM [NGramIndex] AS [idx_table0]
WHERE [idx_table0].[CHARCODE] LIKE '予報%';
検索パターンが N+1 文字以上
検索する文字列パターンが N+1 文字以上の場合には、相関サブクエリを使用します。
N が 2 で、“天気予報では”を検索する SQL です。
SELECT DISTINCT [ID]
FROM [NGramIndex] AS [idx_table0]
WHERE [idx_table0].[CHARCODE]='天気'
AND [ID] IN(
SELECT [ID]
FROM [NGramIndex] AS [idx_table2]
WHERE [idx_table2].[CHARCODE]='予報'
AND [idx_table0].[ID]=[idx_table2].[ID]
AND ([idx_table0].[POSITION]+2)=[idx_table2].[POSITION])
AND [ID] IN(
SELECT [ID]
FROM [NGramIndex] AS [idx_table4]
WHERE [idx_table4].[CHARCODE]='では'
AND [idx_table0].[ID]=[idx_table4].[ID]
AND ([idx_table0].[POSITION]+4)=[idx_table4].[POSITION]);
“天気”の出現位置に対し、ID が同じで +2 の位置に“予報”、+4 の位置に“では”が出現することを条件とします。
文字列パターンが N で割り切れない場合は、次のようになります。
“予報では雨”を検索する SQL です。
SELECT DISTINCT [ID]
FROM [NGramIndex] AS [idx_table0]
WHERE [idx_table0].[CHARCODE]='予報'
AND [ID] IN(
SELECT [ID]
FROM [NGramIndex] AS [idx_table2]
WHERE [idx_table2].[CHARCODE]='では'
AND [idx_table0].[ID]=[idx_table2].[ID]
AND ([idx_table0].[POSITION]+2)=[idx_table2].[POSITION])
AND [ID] IN(
SELECT [ID]
FROM [NGramIndex] AS [idx_table3]
WHERE [idx_table3].[CHARCODE]='は雨'
AND [idx_table0].[ID]=[idx_table3].[ID]
AND ([idx_table0].[POSITION]+3)=[idx_table3].[POSITION]);
“予報”の出現位置に対し、IDが同じで+2の位置に“では”、+3の位置に“は雨”が出現することを条件とします。
端数は、最後の条件の位置で調整します。
検索のSQLは、文字列の長さによって異なるため、次のどちらかの方法で実現します。
- 検索できる文字列の最大長を決め、各長さ用のSELECT文を用意する。
- 文字列の長さに合わせ、動的にSELECT文を生成する。
3.5. 整数型のインデックス
インデックスのCHARCODE列は、固定長文字列ですが、ここに整数型を使用することも出来ます。
実は、最初は、文字型ではなく整数型を使用して試行していました。整数の方が文字よりも処理速度が速いのではないか、と考えたからです。
しかし、実際に比較してみると、文字と整数の速度の違いは確認できませんでした。よって、分かりやすいと思われる文字型での実装方法を優先しましたが、整数型を使用する方法も示しておきます。
整数型を使用する場合には、N-GramのNの値が1,2,4に限定されます。
N 文字の固定長文字列の変わりに、以下の整数型を使用します。
- 1Gram → smallint(16bit)
- 2Gram → int(32bit)
- 4Gram → bigint(64bit)
2Gramのインデックス・テーブルは以下のようになります。
テーブル：NGramIndex
| 列名 | データ型 |
|---|
| CHARCODE | int |
| ID | int |
| POSITION | smallint |
CHARCODE列には、文字コードを整数として格納します。
-
１文字の場合
そのまま16bit整数に変換。 -
２文字の場合
１文字目を左に16bitシフトして２文字目を加える。 -
４文字の場合
１文字目を左に48bitシフト、２文字目を左に32bitシフト、３文字目を左に16bitシフトして４文字目を加える。
検索する文字列パターンも、同様にして整数にします。
検索のSQLは、構造的には文字の場合と同じですが、LIKE演算子を使用する部分にはBETWEENを使用します。
2Gramのインデックスで、“雨”を検索する場合を例とすると、文字‘雨’は16bitのユニコードで0x96E8ですから、0x96E80000～0x96E8FFFFの範囲を対象とすればよいことになります。
注意しなければならないのは符合です。intで0x96E8xxxxは負の値になりますから、BETWEENの部分で大小関係が正しくなるようにしなければなりません。
3.6. 文字列データの正規化
検索対象のテキストは、多少の修正を加えてからインデックスを生成します。
不可視文字の整理
タブ、改行コードなどの不可視文字を検索することが無いのであれば、これらを整理します。
ひとつは、単純にインデックスに追加しない方法で、インデックスのサイズを、多少、小さく出来ます。
もうひとつは、文の区切りとして特定の文字コードに統一し、インデックスに加える方法です。このようにしておくと、文の区切りに対しての前方一致、後方一致検索をすることがきます。
例えば、次のような文字列が検索対象であるとします。
“天気予報によれば雨です。[CR][LF]明日はどうでしょうか？[CR][LF]”
ここで、[CR][LF]は改行コードです。
この文字列は、以下のようにしてからインデックスを生成します。
“[01]天気予報によれば雨です。[01]明日はどうでしょうか？[01]”
不可視文字をまとめて、[01]（数値で1）にし、先頭にも[01]を入れます。
文の区切りに対して、前方一致検索をするのであれば、検索パターンの先頭に[01]を加えて検索します。後方一致検索をするのであれば、検索パターンの末尾に[01]を加えて検索します。
“天気予報”で始まる文を検索したり、“です。”で終わる文を検索することが出来ます。
文字の区別と同一視
ひらがなとカタカナ、アルファベットの大文字と小文字、全角と半角、さらには、‘ヰ’と‘イ’などの区別、同一視の問題です。
インデックス・テーブルに文字列型を使用する場合、検索対象のテキストの文字をそのまま使用すれば、データベースの設定にしたがって処理されます。
インデックス・テーブルに整数型を使用する場合、または、独自の区別、同一視をする場合には、同一視する文字を、同じ文字に変換してインデックスを生成します。
検索の際には、検索する文字列にも同じ変換を施します。
3.7. レコードの削除、更新
検索対象のテーブルに対して、レコードの削除、更新を行う場合には、インデックスも変更しなければなりません。
削除(DELETE)
検索対象のテーブルから、あるIDのレコードを削除する際には、インデックス・テーブルから同じIDのレコードを削除します。
以下のSQLを実行します。
DELETE FROM [NgramIndex] WHERE ID='(削除するID)';
更新(UPDATE)
検索対象のテーブルのレコードを更新する際には、インデックス・テーブルから同じIDのレコードを削除し、新しいテキストに対応したインデックスのレコードを追加します。
- 更新するIDのレコードを削除
- 更新した内容に対応するインデックスのレコードを追加