0

これはインタビューの質問です。

名前で構成されるファイルが与えられた場合、名前がリストに含まれているかどうかを検証するためにどのデータ構造を使用しますか? ファイル内の名前との違いが 1 文字以内であれば、その名前は有効であると言う場合はどうなるでしょうか?

4

3 に答える 3

1

ファイルの名前をトライまたはDAWGに保存することをお勧めします(スペース効率が向上します)。名前が到着したら、データ構造のトラバースを開始します。4つのバリエーションがあります。

  1. 名前が見つかりました->名前は有効です
  2. データ構造の行き止まり->名前に残っている文字数を確認します(1->名前が有効な場合)。それ以外の場合は無効です。
  3. 名前が終了し、構造内のリーフに到達していません->現在の位置に少なくとも1つのリーフがアタッチされているかどうかを確認します(O(アルファベットのサイズ)を取ります)->存在する場合、名前は有効です。それ以外の場合は無効です。
  4. 単語の途中で違いが発生しました->次の文字からトラバースを続けます->エラーは許可されません(段落2と3はこの時点から無効になります)。
于 2012-11-04T09:13:19.953 に答える
1

最初の質問(正確な検索)には、ハッシュテーブルまたはトライを使用できます。ブルームフィルターは、スペースオーバーヘッドで以前に「いいえ」と表示する場合がありますが、明確な「はい」を表示することはできません。

2番目の質問(あいまい検索)では、はるかに高度な手法が必要です。この問題のさまざまな解決策については、 http://blog.srch2.com/2012/03/fuzzy-search.htmlのブログを確認してください。

于 2012-11-05T07:24:46.937 に答える
1

それは文脈によると思います。何百万もの名前があり、履行する契約があり、それを実行する製品がある場合は、それを選び、自分で書くことは忘れてください.

ただし、インタビューの質問のコンテキストでは、考えられるすべての間違いを含むDAWGを提案します。

かなり前に、スペルチェッカーには (有効な単語のリストと照合するのではなく) 間違いの可能性のある単語のリストが含まれていると聞きましたが、それがどの程度正しいかはわかりません。

私は、単語のリストから (間違いのある) 単語を見つける問題に取り組んだことがありますが、それは 1 つの間違いに限定されたものではなく、多くのメモリを利用できるわけではありませんでした。そのため、単語は単純にリストとして格納されました (DAWG にはノードとポインターが必要であり、オーバーヘッドが大きすぎます)。

于 2012-11-03T19:23:50.607 に答える