0

次のような約100 000行の巨大なリストがあります。

  • ipadニュース
  • アブシパッド
  • cddeeffipad
  • 地獄の世界
  • iworldthis など

そして、人気のある部分文字列を見つけたいと思います。この場合、「ipad」が最も人気があり、「world」が 2 位になります。最小の長さは 3 文字または 4 文字にする必要があります。

部分文字列を予測できないため、辞書を使用することはできません。

4

3 に答える 3

4

これは比較的複雑な問題ですが、接頭辞/接尾辞ツリーを使用すると扱いやすいです。これは基本的に、最長共通部分列問題と最長共通部分文字列問題のバリエーションです。-それが私が始めるところです。

このフォームの問題については、実際にはかなりの調査が行われています。上記の用語を使用して検索を絞り込むことができるはずです。

于 2010-11-12T20:04:50.653 に答える
2

これは、時間内に構築できる一般化された接尾辞ツリーを使用して解決できますO(n)。これは事実上、LCS の問題を利用したものです。

于 2010-11-12T20:07:24.187 に答える
0

次のロジック フローを使用して、この問題に取り組みます。

  1. 各単語の接尾辞のセットを抽出します。したがって、「ipadnews」から、「ipadnews」、「padnews」、「adnews」などを取得します。このように、'news' はサフィックスの 1 つになりますが、'ipad' ではありません。

  2. 上記の手順で不足している部分文字列を補うために、プレフィックスも抽出します。「ipad」を含む「ipadnew」、「ipadne」などを取得します。

  3. 上記の部分文字列のそれぞれについて、カウントに向かってハッシュします (例: $hash{$substr}++)。

最後に、単語の頻度を値として持つ長いハッシュテーブルができます。高価な並べ替えの代わりに、最も人気のある 10 の単語だけが必要だとします。その中の任意の単語が現在の最小スコアよりも高いスコアを持つ必要があるという基準を持つセットを最初から保持します。最小スコアで単語を追跡できます。最小スコアを超えるスコアで 11 番目の項目を追加すると、最小スコアで単語を突き止め、最小スコア ポインターを更新します。

ハッシュテーブル内のキーの最大数は 2*k*n で、k は単語の平均長、n は単語の総数です。

于 2010-11-12T20:22:53.860 に答える