こんにちはスタックオーバーフラワー！
200.000 文字列エントリの単語リストがあり、平均文字列長は約 30 文字です。この単語のリストがキーであり、各キーにはドメイン オブジェクトがあります。キーの一部を知っているだけで、このコレクション内のドメイン オブジェクトを見つけたいと考えています。たとえば、検索文字列「kov」は、キー「stackoverflow」と一致します。
現在、私は通常 100 ミリ秒以内にアイテムを見つける三分探索木 (TST) を使用しています。ただし、これは私の要件には遅すぎます。TST の実装は、いくつかの小さな最適化によって改善される可能性があり、ツリーのバランスを取ることができました。しかし、これらのことは、私が目指している 5 倍から 10 倍の速度向上にはつながらないと考えました。非常に遅い理由は、基本的にツリー内のほとんどのノードにアクセスする必要があるためだと思います。
アルゴリズムの速度を改善する方法についてのアイデアはありますか? 私が見なければならない他のアルゴリズムはありますか？
前もってありがとう、オスカー
文字列のサイズに厳密な上限がある場合は、接尾辞配列の使用を検討できます。特殊文字 (null char など) を使用して、すべての文字列を同じ最大長になるまで単純にパディングします。次に、すべての文字列を連結し、それらに接尾辞配列インデックスを作成します。
これにより、 m * log nのルックアップ ランタイムが得られます。ここで、mはクエリ文字列の長さであり、nは結合された文字列の全体の長さです。これでも十分ではなく、mの長さが固定で短く、アルファベット Σ のサイズが制限されている場合 (たとえば、Σ < 128 文字)、追加でq -gram indexを作成できます。これにより、一定時間で取得できます。ただし、q -gram テーブルには Σ m 個のエントリが必要です (= 3 文字だけの場合は 8 MiB、4 文字の場合は 1 GiB!)。
ハッシュ関数を調整することで、 q -gram テーブルのサイズを (最良の場合、指数関数的に) 削減できる可能性があります。可能なすべてのqグラムに一意の番号を割り当てる代わりに、非可逆ハッシュ関数を使用できます。その場合、テーブルは、完全一致に対応する 1 つの接尾辞配列エントリではなく、可能な接尾辞配列インデックスのリストを格納する必要があります。ただし、リスト内のすべてのエントリを考慮する必要があるため、ルックアップは一定ではなくなります。
ところで、q -gram インデックスがどのように機能するかについて、インターネットは役に立たないので、あなたがこのトピックに精通しているかどうかはわかりません。これについては、以前別のトピックで言及しました。したがって、私は学士論文に構築の説明とアルゴリズムを含めました。
私は非常に小さな C# の概念実証を作成しました (C# で作業したと別の方法で述べたため)。動作しますが、2 つの理由で非常に遅いです。まず、接尾辞配列の作成では、単に接尾辞をソートします。これだけでも実行時間はn 2 log nです。はるかに優れた方法があります。SubStringしかし、もっと悪いのは、接尾辞を取得するために使用するという事実です。残念ながら、.NET はこのためにサフィックス全体のコピーを作成します。このコードを実際に使用するには、データを不必要にコピーしないインプレース メソッドを使用するようにしてください。文字列からqグラムを取得する場合も同様です。
m_Data私の例で使用されている文字列を構築しない方が良いかもしれません。SubString代わりに、元の配列への参照を保存し、この配列で作業することですべてのアクセスをシミュレートできます。
それでも、この実装が本質的に一定時間の取得を期待していることは簡単にわかります (ディクショナリが適切に動作している場合)。これは、検索ツリー/トライに勝るものはありません。
class QGramIndex {
private readonly int m_Maxlen;
private readonly string m_Data;
private readonly int m_Q;
private int[] m_SA;
private Dictionary<string, int> m_Dir = new Dictionary<string, int>();
private struct StrCmp : IComparer<int> {
public readonly String Data;
public StrCmp(string data) { Data = data; }
public int Compare(int x, int y) {
return string.CompareOrdinal(Data.Substring(x), Data.Substring(y));
}
}
private readonly StrCmp cmp;
public QGramIndex(IList<string> strings, int maxlen, int q) {
m_Maxlen = maxlen;
m_Q = q;
var sb = new StringBuilder(strings.Count * maxlen);
foreach (string str in strings)
sb.AppendFormat(str.PadRight(maxlen, '\u0000'));
m_Data = sb.ToString();
cmp = new StrCmp(m_Data);
MakeSuffixArray();
MakeIndex();
}
public int this[string s] { get { return FindInIndex(s); } }
private void MakeSuffixArray() {
// Approx. runtime: n^3 * log n!!!
// But I claim the shortest ever implementation of a suffix array!
m_SA = Enumerable.Range(0, m_Data.Length).ToArray();
Array.Sort(m_SA, cmp);
}
private int FindInArray(int ith) {
return Array.BinarySearch(m_SA, ith, cmp);
}
private int FindInIndex(string s) {
int idx;
if (!m_Dir.TryGetValue(s, out idx))
return -1;
return m_SA[idx] / m_Maxlen;
}
private string QGram(int i) {
return i > m_Data.Length - m_Q ?
m_Data.Substring(i) :
m_Data.Substring(i, m_Q);
}
private void MakeIndex() {
for (int i = 0; i < m_Data.Length; ++i) {
int pos = FindInArray(i);
if (pos < 0) continue;
m_Dir[QGram(i)] = pos;
}
}
}
static void Main(string[] args) {
var strings = new [] { "hello", "world", "this", "is", "a",
"funny", "test", "which", "i", "have",
"taken", "much", "too", "far", "already" };
var index = new QGramIndex(strings, 10, 3);
var tests = new [] { "xyz", "aki", "ake", "muc", "uch", "too", "fun", "est",
"hic", "ell", "llo", "his" };
foreach (var str in tests) {
int pos = index[str];
if (pos > -1)
Console.WriteLine("\"{0}\" found in \"{1}\".", str, strings[pos]);
else
Console.WriteLine("\"{0}\" not found.", str);
}
}
これがあなたのためのWAGです。 私はアルゴリズムに精通しており、決してクヌート派ではありません
さて、単純な Trie は、ツリーのルートから開始し、キーの最初の文字から開始して、キーの各文字に一致するブランチを下に移動することにより、文字列キーをエンコードします。したがって、キー「foo」がマップされ(root)->f->fo->foo、値は「foo」ノードが指す場所に格納されます。
キーの先頭から始まる部分文字列だけでなく、キー内の任意の部分文字列を検索しています。
したがって、ノードをその特定の部分文字列を含む任意のキーに関連付ける必要があります。前に示した foo の例では、ノード 'f' と 'fo' の下に foo の値への参照が見つかりませんでした。実行しようとしているタイプの検索をサポートする TST では、3 つのノードすべて (「f」、「fo」、および「foo」) の下で foo オブジェクトを見つけるだけでなく、それも見つけることができます。 「o」と「oo」の下にも。
このタイプのインデックス作成をサポートするために検索ツリーを拡張すると、いくつかの明らかな結果が生じます。まず、ツリーのサイズを爆発させました。驚くほど。保存して効率的に使用できる場合、検索には O(1) 時間かかります。キーが静的なままで、インデックスを分割する方法を見つけて、それを使用する際に大きな IO ペナルティを受けないようにすることができる場合、これは価値があると償却される可能性があります。
次に、小さな文字列を検索すると膨大な数のヒットが発生することがわかります。たとえば、検索用語に最小限の長さを設定しない限り、検索が役に立たなくなる可能性があります。
明るい面としては、トークナイゼーション (zip 圧縮のように) によって、または分岐しないノードを圧縮することによって (つまり、'w'->'o'->' がある場合)、ツリーを圧縮できることもあるかもしれません。 o'-> 最初の 'o' は分岐しないので、安全に 'w'->'oo' に折りたたむことができます)。たぶん、邪悪なお尻のハッシュでさえ、物事を簡単にすることができます...
とにかく、私が言ったようにWAG。
検索文字列の最小サイズ (例: 4 文字) を選択します。文字列エントリのリストを調べて、4 文字の部分文字列ごとに辞書を作成し、部分文字列が表示されるエントリのリストにマッピングします。検索を行うときは、検索文字列の最初の 4 文字に基づいて検索して取得します初期セットを検索し、完全な検索文字列に一致するものだけにその初期セットを絞り込みます。
これの最悪のケースは O(n) ですが、文字列エントリがほぼすべて同一である場合にのみ得られます。ルックアップ ディクショナリは非常に大きくなる可能性が高いため、ディスクに格納するか、リレーショナル データベースを使用することをお勧めします :-)
マシン レジスタのサイズに匹敵するトライ キーを使用すると、利点が得られますか? 32 ビット ボックスを使用している場合は、各文字を個別に比較するのではなく、一度に 4 つの文字を比較できますか? それがあなたのアプリのサイズをどれだけ大きくするかわかりません。
キー値を「ハッシュ」することは可能でしょうか? 基本的に2番目のツリーを持っていると、1番目のツリーへのキーのリストを指しているすべての可能な値が検索されます。
2 つのツリーが必要になります。1 つ目は、ドメイン オブジェクトへのハッシュ値です。2 番目のツリーは、ハッシュ値への検索文字列です。2 番目のツリーには、同じハッシュ値への複数のキーがあります。
ツリー例 1: STCKVRFLW -> ドメイン オブジェクト
ツリー 2: スタック -> STCKVRFLW,STCK オーバー -> STCKVRFLW, VRBRD, VR
したがって、2 番目のツリーで検索を使用すると、1 番目のツリーで検索するキーのリストが得られます。
/編集: 私の友人が、私の q-gram テーブルの構築におけるばかげた仮定を指摘しました。構築ははるかに簡単になり、その結果、はるかに高速になります。これを反映するためにソースコードと説明を編集しました。それが最終的な解決策かもしれないと思います。
以前の回答に対する Rafał Dowgird のコメントに触発されて、コードを更新しました。ただし、かなり長いので、これは独自の回答に値すると思います。既存の文字列をパディングする代わりに、このコードは文字列の元の配列にインデックスを作成します。サフィックス配列は、単一の位置を格納する代わりに、ターゲット文字列のインデックスとその文字列内のサフィックスの位置のペアを格納します。結果として、最初の数字だけが必要になります。ただし、q -gram テーブルの構築には 2 番目の番号が必要です。
新しいバージョンのアルゴリズムは、元の文字列の代わりに接尾辞配列をたどってq -gram テーブルを構築します。これにより、サフィックス配列のバイナリ検索が保存されます。その結果、構築の実行時間はO ( n * log n ) からO ( n ) ( nはサフィックス配列のサイズ) に低下します。
私の最初の解決策と同様に、 を使用するSubStringと不要なコピーが大量に発生することに注意してください。明らかな解決策は、文字列をコピーする代わりに、軽量のラッパーを作成する拡張メソッドを作成することです。次に、比較を少し調整する必要があります。これは、読者の演習として残されています。;-)
using Position = System.Collections.Generic.KeyValuePair<int, int>;
class QGramIndex {
private readonly int m_Q;
private readonly IList<string> m_Data;
private Position[] m_SA;
private Dictionary<string, int> m_Dir;
public QGramIndex(IList<string> strings, int q) {
m_Q = q;
m_Data = strings;
MakeSuffixArray();
MakeIndex();
}
public int this[string s] { get { return FindInIndex(s); } }
private int FindInIndex(string s) {
int idx;
if (!m_Dir.TryGetValue(s, out idx))
return -1;
return m_SA[idx].Key;
}
private void MakeSuffixArray() {
int size = m_Data.Sum(str => str.Length < m_Q ? 0 : str.Length - m_Q + 1);
m_SA = new Position[size];
int pos = 0;
for (int i = 0; i < m_Data.Count; ++i)
for (int j = 0; j <= m_Data[i].Length - m_Q; ++j)
m_SA[pos++] = new Position(i, j);
Array.Sort(
m_SA,
(x, y) => string.CompareOrdinal(
m_Data[x.Key].Substring(x.Value),
m_Data[y.Key].Substring(y.Value)
)
);
}
private void MakeIndex() {
m_Dir = new Dictionary<string, int>(m_SA.Length);
// Every q-gram is a prefix in the suffix table.
for (int i = 0; i < m_SA.Length; ++i) {
var pos = m_SA[i];
m_Dir[m_Data[pos.Key].Substring(pos.Value, 5)] = i;
}
}
}
maxlen使用法は、コンストラクターに必要な引数を除いて、他の例と同じです。