0

これは、stackoverflowでのほとんどのトライの問題とは少し異なります（はい、私は検索と読み取りに時間を費やしました）ので、ご容赦ください。

私は次のような単語を含むファイルAを持っています：allow *、apolog*など。合計で数万のそのようなエントリがあります。そして、最大数千の単語を含むテキストの本文を含むファイルBがあります。ファイルBのテキストの単語とファイルAの単語を一致させたい。

例：

ファイルBの「謝罪」はファイルAの「謝罪*」と一致します

ファイルBの「a」は「allow*」にも「apolog*」にも一致しません

FILEBの「apologizetomenoworelseiwillkillyou」もFILEAの「apolog*」と一致します

これを達成するのに役立つアルゴリズム/データ構造（Pythonで実行可能であることが望ましい）を誰かが提案できますか？私が調べた試みは、接頭辞を単語全体に一致させることに関するもののようですが、ここでは、単語全体を接頭辞に一致させています。ステミングアルゴリズムはルールが固定されているため問題外ですが、この場合、私の接尾辞は何でもかまいません。時間がかかりすぎるため、ファイルAのリスト全体を繰り返し処理したくありません。

これが紛らわしい場合は、明確にさせていただきます。ありがとう。

4

4 に答える 4

1

あなたが探しているものを理解しているなら、ファイルBの特定の完全な単語に一致するファイルAのすべてのプレフィックスを表示できるようにする必要があります。トライデータ構造を使用すると、単一のプレフィックスを完全な単語のリストに一致させることができます。しかし、あなたは反対の方向に進む必要があります。

その場合でも、ルックアップテーブルを使用して結果を逆にし、トライを使用してマッチングを行うことができます。アルゴリズムは次のとおりです。

  • ファイルBの単語を繰り返し、それらをトライに入れます。
  • ファイルAのプレフィックスを繰り返し処理し、トライから一致するものを見つけます。
    • 一致するたびに、一致した単語でインデックス付けされたプレフィックスをリストの辞書に追加します。

アルゴリズムを実装するコードを次に示します。名前付きのtrieクラスと、引数として渡されるiterablesが必要です（Trieすべて の値を同時にメモリに入れたくない場合は、ジェネレーターを使用してください）。wordsprefixes

def matchPrefixes(words, prefixes):
    """Returns a word-to-prefix lookup table."""

    trie = Trie()
    for word in words:
        trie.add(word)

    lookupTable = defaultdict(list)
    for prefix in prefixes:
        matchedWords = trie.matchPrefix(prefix)

        for word in matchedWords:
            lookupTable[word].append(prefix)

    return lookupTable

これは、特に単語のリストが接頭辞のリストよりもはるかに短い場合、時間とメモリの両方でかなり効率的であるはずです。どの単語とも一致しないプレフィックスは、トライに対してチェックされた後、メモリを使用しません。

于 2012-08-03T06:54:18.850 に答える
1

すべてのプレフィックスをハッシュテーブルに入れます。次に、B の各単語を取得し、ハッシュテーブルでそのすべてのプレフィックスを調べます。ヒットした場合は、一致したことを示します。

したがって、ハッシュテーブルには「許可」と「謝罪」が含まれます。「お詫び」の場合は、「a」、「ap」の順に検索し、「apolog」を検索して一致するものを見つけます。

于 2012-08-03T04:34:47.347 に答える
1

各ファイルに 100,000 語があると仮定します。

並べ替え = n*log(n) 二分探索ルックアップ = log(n)

したがって、これは最悪のケースです n*log(n)

つまり、100,000 * log(100, 000) = 100,000 * 11 = 10^6 = ほぼ瞬時

このような小さなファイルには特別なものは必要ないと思います。単純に並べ替えてバイナリ検索します。

__author__ = 'Robert'

from bisect import bisect_right

file_a = """hell*
wor*
howard*
are*
yo*
all*
to*""".splitlines()

file_b = """hello world how are you all today too told town""".split()

a_starts = sorted(word[:-1] for word in file_a) #can do this easily if only 100, 000 words as you say.

def match(word):
    pos = bisect_right(a_starts, word)
    #assert 0 <= pos < len(a_starts)
    matched_word = a_starts[pos - 1]
    return matched_word if word.startswith(matched_word) else None

for word in file_b:
    print(word, " -> ", match(word))

"""
hello  ->  hell
world  ->  wor
how  ->  None
are  ->  are
you  ->  yo
all  ->  all
today  ->  to
too  ->  to
told  ->  to
town  ->  to
"""
于 2012-08-03T09:12:43.847 に答える
1

ファイル B の単語数がファイル A の接頭辞よりもはるかに多い場合は、接頭辞のトライを作成して、その中の単語と照合することもできます。

Trie の仕組みを理解すれば、はるかに簡単になります。Trie は、以下に示すように、文字列から構築されたツリーです。Trie 内の文字列の一致は、ルートからリーフの 1 つに移動するプロセスです。

あなたの問題では、接頭辞をトライに入れて単語を探す場合、トライの内部ノードのいくつかを接頭辞の終端としてマークする必要があります。トライで単語を探すとき、接頭辞の終端としてマークされているノードに到達するたびに、その接頭辞を単語に「一致」として追加します。（それから次の手紙に進みます）。

これはまさに@Blckknghtのソリューションの逆のソリューションです。どちらが効率的かは、ファイル A とファイル B のどちらが大きいかによって異なります。

@Blckknght のソリューションでは、Trie の各ノードは、ノードを含む単語 (そのパス) のセットによってマークされます。プレフィックスの検索は、プレフィックスの最後の文字で終了します。停止すると、検索が停止する Trie ノードを取得し、ノードで一致としてマークされたセットをプレフィックスに追加します。

誰にとっても役立つ場合は、疑似コードをいくつか書きます。

「アルゴリズム」部分にいくつかのコードを見つけることができるwikiから試してください

ここに画像の説明を入力

于 2012-08-03T08:18:49.913 に答える