4

長い (> 1000 項目) 単語のリストがあり、残りの単語がすべて「著しく異なる」まで、他の単語と「あまりにも似ている」単語を削除したいと考えています。たとえば、編集距離 D 内に 2 つの単語が入らないようにします。

一意のソリューションは必要ありません。また、正確に最適である必要もありませんが、(Python では) 適度に高速であり、あまりにも多くのエントリを破棄しないようにする必要があります。

どうすればこれを達成できますか？ありがとう。

編集：明確にするために、編集距離を測定するPythonルーチンをグーグルで検索できます。問題は、これを効率的に行う方法であり、おそらく、D の「自然な」値を見つける方法です。おそらく、すべての単語からある種のトライを構築し、剪定することでしょうか?

4

3 に答える 3

3

を使用できます。bk-tree各アイテムを追加する前に、他のアイテムから距離D以内にないことを確認してください（このアイデアのコメントにある@DietrichEppに感謝します。

このレシピはbk-treeに使用できます（ただし、同様のレシピは簡単に変更できます）。単に2つの変更を加えます：行を変更します：

def __init__(self, items, distance, usegc=False):

に

def __init__(self, items, distance, threshold=0, usegc=False):

そして、行を変更します

        if el not in self.nodes: # do not add duplicates

に

        if (el not in self.nodes and
            (threshold == None or len(self.find(el, threshold)) == 0)):

これにより、アイテムが追加されたときに重複がないことが保証されます。次に、リストから重複を削除するコードは次のとおりです。

from Levenshtein import distance
from bktree import BKtree
def remove_duplicates(lst, threshold):
    tr = BKtree(iter(lst), distance, threshold)
    return tr.nodes.keys()

これは、距離関数をpython-Levenshteinパッケージに依存していることに注意してください。これは、bk-treeによって提供されるものよりもはるかに高速です。python-LevenshteinにはCでコンパイルされたコンポーネントがありますが、インストールする価値があります。

最後に、単語数を増やして（からランダム/usr/share/dict/wordsに取得）パフォーマンステストを設定し、それぞれの実行にかかった時間をグラフ化しました。

import random
import time
from Levenshtein import distance
from bktree import BKtree

with open("/usr/share/dict/words") as inf:
    word_list = [l[:-1] for l in inf]

def remove_duplicates(lst, threshold):
    tr = BKtree(iter(lst), distance, threshold)
    return tr.nodes.keys()

def time_remove_duplicates(n, threshold):
    """Test using n words"""
    nwords = random.sample(word_list, n)
    t = time.time()
    newlst = remove_duplicates(nwords, threshold)
    return len(newlst), time.time() - t

ns = range(1000, 16000, 2000)
results = [time_remove_duplicates(n, 3) for n in ns]
lengths, timings = zip(*results)

from matplotlib import pyplot as plt

plt.plot(ns, timings)
plt.xlabel("Number of strings")
plt.ylabel("Time (s)")
plt.savefig("number_vs_time.pdf")

ここに画像の説明を入力してください

数学的に確認しないと、2次式ではないと思います。実際にn log nは、bkツリーへの挿入がログ時間演算である場合は理にかなっていると思います。最も注目すべきは、5000未満の文字列で非常に高速に実行されることです。これは、OPの目標であることが期待されます（従来のforループソリューションでは不可能だった15000では妥当です）。

于 2013-01-09T05:36:18.757 に答える
2

試行は役に立ちませんし、ハッシュ マップも役に立ちません。これらは、このような空間的で高次元の問題にはまったく役に立ちません。

しかし、ここでの本当の問題は、「効率的」という要件が明確に規定されていないことです。「効率的」とはどのくらいの速さですか？

import Levenshtein

def simple(corpus, distance):
    words = []
    while corpus:
        center = corpus[0]
        words.append(center)
        corpus = [word for word in corpus
                  if Levenshtein.distance(center, word) >= distance]
    return words

ハード ドライブにある「アメリカ英語」辞書から均一に選択された 10,000 語に対してこれを実行し、距離が 5 のセットを探し、約 2,000 エントリを生成しました。

実質 0m2.558s
ユーザー 0m2.404s
システム 0m0.012s

では、問題は「どれだけ効率的で十分か」ということです。要件が指定されていないため、このアルゴリズムが機能するかどうかを判断するのは非常に困難です。

うさぎの穴

もっと速くしたい場合は、次のようにします。

VP ツリー、BK ツリー、またはその他の適切な空間インデックスを作成します。コーパス内の各単語について、インデックス内のすべての単語から適切な最小距離がある場合、その単語をツリーに挿入します。空間インデックスは、この種のクエリをサポートするように特別に設計されています。

最後に、目的の最小距離を持つノードを含むツリーができます。

于 2013-01-09T06:23:07.190 に答える
0

あなたの考えは間違いなく興味深いものです。このページには、トライで編集距離を高速に計算するための優れたセットアップがあり、単語リストを 1,000 ではなく数百万に拡張する必要がある場合、間違いなく効率的です。

頑張ってください。問題の楽しい表現のように思えます!

于 2013-01-09T05:43:09.607 に答える