コメントで指摘したように、接頭辞と接尾辞のケースは、一般的な部分文字列のケース (#2) でカバーされます。すべての接頭辞と接尾辞は、定義上、部分文字列でもあります。したがって、解決する必要があるのは、一般的な部分文字列の問題だけです。
静的辞書があるので、それを比較的簡単に前処理して、部分文字列をすばやくクエリできる形式にすることができます。サフィックス ツリーを使用してこれを行うこともできますが、データの単純な並べ替えられたフラット ベクトルを作成して処理する方がはるかに簡単なので、ここで説明します。
したがって、最終的な目標は、ソートされたサブワードのリストを作成して、バイナリ検索を実行して一致を見つけることです。
まず、クエリ フラグメントに一致する最長の部分文字列を見つけるために、各単語のすべての可能な部分文字列をリストする必要はなく、単にすべての可能なサフィックスをリストする必要があることに注意してください。これは、すべての部分文字列が単に接尾辞の接頭辞と考えられるためです。（わかりましたか？初めて遭遇したときは少し戸惑いますが、最終的にはシンプルで非常に便利です。）
したがって、各辞書の単語のすべての接尾辞を生成し、それらをすべて並べ替えると、辞書の単語のいずれかで特定の部分文字列を見つけるのに十分ですstd::lower_bound。クエリ フラグメントで始まる最初のサフィックス。次に、上限 ( std::upper_bound) を見つけます。これは、クエリ フラグメントで始まる最後の接尾辞の 1 つ後ろになります。範囲 [lower, upper[] 内のすべての接尾辞はクエリ フラグメントで始まる必要があるため、これらの接尾辞の元のすべての単語にはクエリ フラグメントが含まれます。
さて、実際にすべての接尾辞を実際にスペルアウトすると、非常に多くのメモリが必要になることは明らかですが、その必要はありません。接尾辞は、単語への単なるインデックス、つまり接尾辞が始まるオフセットと考えることができます。したがって、可能なサフィックスごとに 1 組の整数のみが必要です。1 つは (元の) 単語インデックス用で、もう 1 つはその単語のサフィックスのインデックス用です。(辞書のサイズに応じて、これら 2 つを巧みにまとめると、スペースをさらに節約できます。)
要約すると、必要なことは次のとおりです。
- すべての単語について、すべての単語と接尾辞のインデックス ペアの配列を生成します。
- 接尾辞 (数値ではありません) として意味上の意味に従ってこれらを並べ替えます。
std::stable_sortカスタムコンパレータを使用することをお勧めします。これは最長の手順ですが、辞書は静的であるため、オフラインで 1 回実行できます。
- 特定のクエリ フラグメントについて、並べ替えられたサフィックス インデックスの下限と上限を見つけます。この範囲内の各サフィックスは、一致する部分文字列 (単語インデックスの単語のサフィックス インデックスから始まる、クエリの長さ) に対応します。一部の単語は複数回一致する場合があり、一致が重複する場合さえあることに注意してください。
明確にするために、「スカンク」と「チーズ」という単語で構成される辞書のごくわずかな例を次に示します。
「skunk」の接尾辞は、「skunk」、「kunk」、「unk」、「nk」、および「k」です。インデックスとして表現すると、 です0, 1, 2, 3, 4。「チーズ」の接尾辞は、「cheese」、「heese」、「eese」、「ese」、「se」、および「e」です。インデックスは0, 1, 2, 3, 4, 5.
「スカンク」は非常に限られた架空の辞書の最初の単語なので、インデックス 0 を割り当てます。「チーズ」はインデックス 1 です。したがって、最後の接尾辞は次のとおり0:0, 0:1, 0:2, 0:3, 0:4, 1:0, 1:1, 1:2, 1:3, 1:4, 1:5です。
これらのサフィックスを並べ替えると、次のサフィックス ディクショナリが生成されます (説明のために、実際の対応するテキスト部分文字列を追加しました)。
0 | 0:0 | cheese
1 | 0:5 | e
2 | 0:2 | eese
3 | 0:3 | ese
4 | 0:1 | heese
5 | 1:4 | k
6 | 1:1 | kunk
7 | 1:3 | nk
8 | 0:4 | se
9 | 1:0 | skunk
10 | 1:2 | unk
クエリ フラグメント「e」を考えてみましょう。「e」はクエリ「e」以上の最初のサフィックスであるため、下限は 1 です。4 ("heese") は "e" より大きい最初のサフィックスであるため、上限は 4 です。したがって、1、2、および 3 の接尾辞はすべてクエリで始まるため、それらが由来するすべての単語には、クエリが部分文字列として含まれています (クエリの長さの接尾辞インデックス)。この場合、これら 3 つのサフィックスはすべて、異なるオフセットで「cheese」に属しています。
どの単語の部分文字列でもないクエリ フラグメント (この例では "a" など) の場合、一致するものがないことに注意してください。このような場合、下限と上限は等しくなります。