8

単語と説明で構成されるクロスワード パズルを解くための大規模なデータベースがあります。私のアプリケーションでは、特定の長さの単語と特定の位置の文字を検索できます (これは難しい方法で行われます... すべての単語を調べて、それぞれを確認します)。さらに、説明による検索 (必要な場合)

たとえば、単語 _ _ A _ _ B を検索します (6 文字の単語、3 番目の文字 A と最後の B)

検索が非常に高速になるように、単語にインデックスを付けたいと思います。私の最初のアイデアは、バランスの取れたツリー構造を使用することでした。他の提案はありますか?

4

5 に答える 5

9

さて、変なことを提案しますが、私は長い間C++使用しており、ライブラリBoostを見に来ました。MultiIndex

このライブラリのアイデアは、1 つのコレクションを作成することですが、それを照会するさまざまな方法があります。実際、データベースをモデル化できます。

それでは、単語をテーブルに入れ、必要なインデックスを配置しましょう。

word                     |length|c0|c1|c2| ... |c26|
-------------------------|------|--|--|--| ... |---|
Singapour                |9     |S |i |n | ... |0  |

クエリは次のようになります。

Select word From table Where length=9 And c2='n' And c8='u';

簡単ですね。

最大限の効率を得るには、テーブルを長さでパーティション分割し、インデックス (cX 列ごとに 1 つ) をパーティションに対してローカルにする必要があります。

インメモリ ソリューションの場合、長さごとに 1 つのコンテナーがあり、長さと同じ数のインデックスが含まれます。各インデックスは、並べ替えられたリストを指すハッシュ テーブルです (マージが容易になります)。

python の説明は次のとおりです。

class Dictionary:
  def __init__(self, length):
    self.length = length
    self.words = set([])
    self.indexes = collections.defaultdict(set)

  def add(self, word):
    if len(word) != self.length:
      raise RuntimeException(word + ' is not ' + `self.length` + ' characters long')

    if word in self.words:
      raise RuntimeException(word + ' is already in the dictionary')

    self.words.add(word)

    for i in range(0,length):
      self.indexes[(i,word[i])].add(word)

  def search(self, list):
    """list: list of tuples (position,character)
    """
    def compare(lhs,rhs): return cmp(len(lhs),len(rhs))

    sets = [self.indexes[elem] for elem in list]
    sets.sort(compare)
    return reduce(intersection, sets)

lengthハッシュのサイズを最小限に抑えて検索を改善するために、私は自発的に引数を提供しました。また、セットは長さでソートされているため、交差の計算が改善されます:)

必要に応じて、他のソリューションと比較してテストしてください:)

于 2010-02-19T14:30:35.727 に答える
4

この質問:文字が欠落している単語を検索するための優れたアルゴリズムとデータ構造は? あなたが求めているものとまったく同じように始まりましたが、その後、かなり違った簡単なものに編集されました. それでも、そこにいくつかのアイデアを見つけることができます。

つまり、辞書全体をメモリにロードし、単語の長さに基づいて単語をグループに分割することを誰もが推奨しています。そこから、さまざまな方向に進むことができます。使いたいメモリが多ければ多いほど、より速く進むことができます。

良い提案の 1 つは、特定の文字が特定の位置にある、特定の長さの単語のリストのハッシュ テーブルを保持することです。次のようにビルドできます (Python で):

# Build a whole lot of sorted word lists
wordlists = collections.defaultdict(list)
for word in sorted(all_words):
    for position, letter in enumerate(word):
        wordlists[len(word), position, letter].append(word)

B で終わる 6 文字の単語が必要な場合は、求めるだけwordlists[6, 5, 'B']で完全なリストが得られます。のように、複数の文字を知っている場合..A..Bは、最も短いリストを選択し、各単語を目的のパターンに対してテストできます。私のコンピューターの辞書には、B で終わる 6 文字の単語が 21 個しかなく、そのうち SCARAB のみが一致します。

于 2010-02-18T16:17:48.650 に答える
2

データベースを使用するため、サフィックステーブルを作成します。
例えば ​​： 

  Suffix          |   WordID   | SN
  ----------------+------------+----   
  StackOverflow           10      1
  tackOverflow            10      2
  ackOverflow             10      3
  ckOverflow              10      4
  kOverflow               10      5
  ...


このテーブルを使用すると、次のように、特定の位置に特定の文字を含むすべての単語を簡単に取得できます。

SELECT WordID FROM suffixes
WHERE suffix >= 't' AND suffix < 'u' AND SN = 2

't'位置に含まれるすべての単語を取得します2。

更新：スペースを節約し、速度を少し犠牲にしたい場合は、接尾辞配列を使用できます。

すべての単語を区切り文字、つまり、を含む行（配列）に格納し、$charsへのポインターを持つ接尾辞配列を作成できます。これで、charが与えられると、cそれを含む単語のすべてのインスタンスをかなり速く見つけることができます。それでも、それが正しい位置にあるかどうかを調べる必要があります。
（sからの距離を確認することにより$）

おそらく上記の手法を使用すると、元のプログラムのすべての単語を検索するよりも検索が10倍速くなります。

更新2：たとえば、「ne」などのサフィックスを見つける必要があるユーティリティの1つでデータベースアプローチを使用しましたが、この特定の問題に合わせて調整（最適化）するのを忘れました。

接尾辞として1つの文字を保存するだけです。

  Suffix   |   WordID   | SN
  ---------+------------+----   
  S                10      1
  t                10      2
  a                10      3
  c                10      4
  k                10      5
  ...

これは多くのスペースを節約します。これで、クエリは次のようになります

SELECT WordID FROM suffixes
WHERE suffix = 't' AND SN = 2
于 2010-02-18T13:49:41.237 に答える
1

Suffix Treeまたは Trieを使用できます。

于 2010-02-18T13:54:21.203 に答える
1

ある種のトライ (おそらく三分探索木) に情報を保存することができます。トライを使用した部分検索のアルゴリズムは、Sedgewick と Bentley によるこの論文のセクション 6 で説明されています。もちろん、さまざまな長さの単語に対してさまざまな試みが必要です。この論文によると、部分検索アルゴリズムでは、n 個の k 個の長さの単語のトライで指定されている s 個の文字に対して O(n^((ks)/k)) の時間が必要です。

于 2010-02-19T14:55:00.653 に答える