文字列のセットが与えられた場合、セット内の別の文字列の部分文字列であるすべての文字列を削除する必要があります。部分文字列は、任意の位置に発生する可能性があります。文字列の少なくとも 50% は、他の文字列の部分文字列になると予想しています。私の文字列は、大規模な自然言語コーパスからの n-gram です。
たとえば、("the big car", "big car", "at the big car", "bu a big car", "buy a big", "bu a big house") とすると、結果は ("大きな車で」、「大きな車を買う」、「大きな家を買う」）; 出力の順序は重要ではありません。
私のセットには 100,000 の文字列があるため、各文字列を他のすべての文字列に対してブルート フォース テストすることはできません。
この問題の標準的な解決策を知っている人はいますか?
または、誰かが私が持っていたいくつかの考えに追加できますか:
最初に文字列を並べ替えると、文字列の先頭 (および文字列の末尾を逆に並べ替える) で部分文字列を簡単に選択できるはずですか? 他の場所で部分文字列を処理する必要があります。
ツリー構造を使用しますか? 次のようなものですか？(i) 各文字列に START および END トークンを追加します。(ii) ツリーの最初のノードは START です。(iii) 文字列 "big car" --> 新しい分岐 START-big-car-END ですが、"the big car" が追加されると、分岐は START-the-big-car-END になります。(iv) すべての文字列が挿入されたら、START から END までのすべてのパスを読み取ります。潜在的に大きな単語のセット (少なくとも 1000 の) を考えると、これについてはわかりません。また、文中に同じ単語が複数回出現する問題。
次に処理される文字列を、以前に削除された一連の文字列と最初に比較できるように、ブルート フォースにある種のメモリを追加できますか?