4

たとえば 1000 語の辞書ファイルを読み込んでから、いくつかの段落があると言う別のドキュメントをチェックすることで、バイナリ検索ツリーをスペル チェッカーにする最も効率的な方法を考えています。

4

8 に答える 8

8

三分木トライの方が効率的だろう

于 2008-12-05T02:22:19.593 に答える
3

二分探索木の使用に固執していますか? ブルーム フィルターは、おそらくより効率的なデータ構造です。

于 2008-12-05T03:34:11.087 に答える
1

このサイトは、 Java で実装されているため、役に立ちます。

于 2011-06-12T03:07:19.873 に答える
1

特定の単語が辞書に存在するかどうか (つまり、そのスペルが正しいかどうか) を確認するだけの場合は、二分探索木が求めているものではないと思います。その情報を保存するためのより良い方法は、ツリーの連続する各ノードが 1 文字であるツリー スタイルであり、最後のノードへのパスを読み取ると、その単語のスペルがわかります。また、語尾を示すマーカーを追加する必要があります。

例: 辞書に次の単語があるとします: car、cart、cat、cup、cut

- C
  - A
    - R
      - end
      - T
    - T
      - end
  - U
    - P
      - end
    - T
      - end

単語が存在するかどうかを確認するには、各文字を個別に調べ、それが現在のノードの子に存在するかどうかを確認します。

Check for "cat"
Does "C" exist at the root level? Yes, move to the next letter.
Does "A" exist underneath C? Yes, move on.
Does "T" exist underneath A? Yes, move on.
Is there a word ending after the T? Yes. Word exists.

Check for "cu"
Does "C" exist at the root level? Yes, move to the next letter.
Does "U" exist at the root level? Yes, move to the next letter.
Is there a word ending after the U? No. Word does not exist.

この情報をどのように保存するかは、あなた次第です。Steven が指摘したように、Ternary Search Trieが最適な方法である可能性があります。各ノードには 27 の可能な子ノードがあります。

于 2008-12-05T03:16:24.663 に答える
0

示唆されているように、トライは二分木よりも効率的ですが、ハッシュマップを使用して各単語をハッシュすることができます。小さな辞書 (1000 エントリ) があります。ドキュメントをトラバースするときに、単語がハッシュマップに含まれているかどうかを確認します。そうでない場合、単語のスペルが間違っていると見なされます。

これでは、スペルミスの単語を修正することはできません。はいまたはいいえ（正しいかどうか）を示すだけです。

間違った単語のスペル候補が必要な場合は、ファイル内の単語から始めて、1 編集距離離れたすべての単語を生成し、これらを最初の単語の子として追加します。このようにして、グラフを作成しています。最大速度と正確さを得るには、2 レベル深く進みます。辞書にある単語ノードを生成すると、候補のリストに追加できます。最後に、可能な提案のリストを返します。

より良いスペル チェックを行うには、発音一致も追加してみてください。

sea yuh -> see yah

この方法 (文字列のグラフを 1 編集で作成する方法) は「遅い」です。しかし、それは良い学問的な練習です。実行時間は O(n^branches) です。

興味がある場合は、私が自分で作成したものへのリンクを次に示します (楽しみのために): https://github.com/eamocanu/spellcheck.graph

いくつかのサンプル グラフ: https://github.com/eamocanu/spellcheck.graph/tree/master/graph%20photos

グラフを生成する UI コンポーネントも追加しました。これは外部ライブラリです。

于 2011-12-15T21:26:08.783 に答える
0

自動提案/プレフィックス検索も行う必要がある場合は、パトリシア ツリーまたは基数ツリーを検討する価値があります。

于 2008-12-05T02:26:26.917 に答える
0

これは宿題の質問であるため、単純な古いバイナリ ツリー (赤黒ツリー、AVL ツリー、基数ツリーなどは使用しない) を使用する必要があると仮定します。答えは、単語リストからツリーを作成するときに、ツリーのバランスを保つようにすることです。1 つのアプローチは、リストを読み込む前にランダム化することです。これにより、妥当な結果が得られます。ただし、入力シーケンスを並べ替え (ツリーが使用するものと同じ比較を使用) すると、より良い結果を得ることができます。その後、要素がなくなるまで、中間点を返す入力を再帰的に再分割します。その結果、バランスの取れたツリーになります。

私は C# でそれを行うための 3 つの異なる方法を試しました。

private static IEnumerable<T> BinaryTreeOrder<T>(IList<T> range, int first, int last)
{
  if (first > last)
  {
    yield break;
  }

  int mid = (first + last) / 2;
  yield return range[mid];
  foreach (var item in BinaryTreeOrder(range, first, mid - 1))
  {
    yield return item;
  }
  foreach (var item in BinaryTreeOrder(range, mid + 1, last))
  {
    yield return item;
  }    
}

private static void BinaryTreeOrder<T>(IList<T> range, int first, int last, 
                                       ref IList<T> outList)
{
  if (first > last)
  {
    return;
  }

  int mid = (first + last) / 2;
  outList.Add(range[mid]);
  BinaryTreeOrder(range, first, mid - 1, ref outList);
  BinaryTreeOrder(range, mid + 1, last, ref outList);
}

private static void BinaryTreeOrder<T>(IList<T> range, int first, int last, 
                                       ref BinaryTree<T> tree) where T : IComparable<T>
{
  if (first > last)
  {
    return;
  }

  int mid = (first + last) / 2;
  tree.Add(range[mid]);
  BinaryTreeOrder(range, first, mid - 1, ref tree);
  BinaryTreeOrder(range, mid + 1, last, ref tree);
}
于 2011-04-20T20:27:55.200 に答える
0

あなたが示した例では、完全に愚かなアルゴリズムを使用しない限り、PC では、ユーザーが表示する最初の結果を読み取るのにかかる時間の約 1% が操作全体にかかるため、パフォーマンスは無関係である可能性があります。 . それでも、パフォーマンスが問題になるほど問題が大きいと思います。

辞書ファイルが事前に並べ替えられている場合（ほとんどの場合）、テキストが辞書に比べて小さい場合、テキストを並べ替えて、おそらく重複を削除し、両方のリストを並べて繰り返します-サイド マージソートと同じ手順を使用しますが、マージされたリストを出力する代わりに、各テキスト単語が辞書にあるかどうかを報告します。

これは、ソートで約 M log M の比較に加えて、反復で最大 N + M の比較でジョブを実行します (おそらく少ないですが、複雑さがなくなるわけではありません)。これは、1 回限りの操作の最適な複雑さにかなり近いです。N の線形項を取り除くには、ディスクからディクショナリ全体をまったく読み取らない方法を見つける必要があります。特に単語が非常に短いことを考えると、ファイルを bsearch できると確信していますが、N が小さい場合、その場所を探す方が実際にデータにシリアル アクセスするよりも速いかどうかは誰にもわかりません。

次の特徴があります。

  • 辞書をメモリに保持する必要はなく、テキストのみを保持します。
  • それでも、ディクショナリ ファイルを 1 回だけパスします。
  • ディクショナリの高価な処理は行いません。

もちろん、辞書ファイルが事前にソートされていない場合、これは機能しません。次のスペルチェック操作のために辞書をメモリ内に保持できる場合は、I/O のコストとそれを次のように処理するコストを償却できます。長期的には勝利となる、いくつかの異なるテキストにまたがるツリー。

辞書が非常に大きい場合は、言語のさまざまな単語の相対頻度に従って重み付けされた不均衡なツリーに相当する、前処理された形式でディスクに保存することでメリットが得られる場合があります。次に、小さなテキストに対して O(N) 未満のディスク アクセスを実行できます。ほとんどの OS では、ファイルをメモリにロードする必要はまったくなく、ファイルを mmap して OS に心配させます。大きな辞書の場合、「ジメチル」で始まる単語を含むクラスター全体に触れる必要はありません。

もう 1 つの考慮事項は、ディクショナリのスプレイ ツリーです。スプレイ ツリーは、頻繁に使用される値をすばやく見つけられるようにするために、調べているうちにバランスを崩します。ほとんどのテキストは少数の単語を繰り返し使用するため、テキストがオーバーヘッドを正当化するのに十分な長さである場合、最終的にはこれが優先されます。

上記の両方は、文字列の場合、トライは通常のツリーに勝るというスティーブン・A・ロウの指摘に従います。ただし、既製のスプレイ トライが見つかるかどうかはわかりません。

于 2008-12-05T02:55:11.040 に答える