1

文字列（マルチワード）の膨大なリスト（200000）があります。これらの文字列間の単語一致のコンマ配列に基づいて、これらの文字列をグループ化します。このための低計算時間アルゴリズムは考えられません

" AB500 "
"バスAB500 "
"ニュースCA "
"ニュースCABLAH"

私の計画はでし
た。それらを単語にトークン化します。
b。グローバル配列トークンを作成します
c。それらの文字列を一般的なトークンと比較します。

ご想像のとおり、これは役に立ちません。このためのアルゴリズムを提案できますか？私はこれをPythonで書いています。

4

4 に答える 4

2

200000はそれほど多くありません、これを行うことができます

  1. 各文字列を分割してトークンを取得します。例: "News CA BLAH" -> ["Blah", "CA", "News"]
  2. リストの各長さの辞書エントリを作成します。たとえば、["Blah", "CA", "News"] の場合はすべての組み合わせを順番に作成します
  3. 辞書をループしてグループを表示するだけです

コード例:

data="""AB 500
Bus AB 500
News CA
News CA BLAH"""

def getCombinations(tokens):
    count = len(tokens)
    for L in range(1,count+1):
        for i in range(count-L+1):
            yield tuple(tokens[i:i+L])

groupDict = {}
for s in data.split("\n"):
    tokens = s.split()
    for groupKey in getCombinations(tokens):
        if groupKey not in groupDict:
            groupDict[groupKey] = [s]
        else:
            groupDict[groupKey].append(s)

for group, values in groupDict.iteritems():
    if len(values) > 1:
        print group, "->", values

それは出力します：

('News', 'CA') -> ['News CA', 'News CA BLAH']
('AB',) -> ['AB 500', 'Bus AB 500']
('500',) -> ['AB 500', 'Bus AB 500']
('CA',) -> ['News CA', 'News CA BLAH']
('AB', '500') -> ['AB 500', 'Bus AB 500']
('News',) -> ['News CA', 'News CA BLAH']
于 2009-11-12T04:58:55.297 に答える
1

このようなことを意味しますか？

>>> from collections import defaultdict
>>> L=["AB 500",
... "Bus AB 500",
... "News CA",
... "News CA BLAH"]
>>> d=defaultdict(list)
>>> for s in L:
...     for w in s.split():
...         d[w].append(s)
... 
>>> print d["News"]
['News CA', 'News CA BLAH']
>>> print d["CA"]
['News CA', 'News CA BLAH']
>>> print d["500"]
['AB 500', 'Bus AB 500']
于 2009-11-12T04:57:51.973 に答える
1

単語の繰り返しがユースケースにとって重要な機能でない限り、セットをお勧めします。すなわち:

thestrings = [
"AB 500",
"Bus AB 500",
"News CA",
"News CA BLAH",
]

thesets = dict((s, set(s.split())) for s in thestrings)

similarities = dict()
for s in thestrings:
  for o in thestrings:
    if s>=o: continue
    sims = len(thesets[s] & thesets[o])
    if not sims: continue
    similarities[s, o] = sims

for s, o in sorted(similarities, similarities.get, reverse=True):
  print "%-16r %-16r %2d" % (s, o, similarities[s, o])

これはあなたが探しているものに近いですか？それはあなたが望むようにあなたが与えた4つの文字列を分類しますが、もちろんそれは非常に貧弱なサンプルなので、私は二重にチェックしています;-)。

于 2009-11-12T05:30:10.913 に答える
0

リストに「AB 500 News CA」という文字列が追加されたらどうなるでしょうか? 文字列の 2 つのグループをマージする必要がありますか? そうでない場合、文字列のリストを分割する方法とその理由は?

このような問題の非常に一般的なワークフロー (私が正しく理解していれば) は次のようになります。

  1. 逆索引/全ペア類似検索/シムハッシュで候補ペア一覧を取得
  2. 各ペアのいくつかの距離関数を計算し、それらを単一の重みに結合します
  3. 重み付けされた各ペア ((a、b)、重み) はグラフのエッジを表し、階層的クラスタリング/べき乗反復を介して「単語一致グループ」にクラスタリングできます。
于 2009-11-13T10:29:02.630 に答える