1

我有大量的字符串（多字）列表（200000）。我想根据这些字符串之间的单词匹配的comman数组对这些字符串进行分组。我想不出一个低计算时间的算法

“ AB 500 ”
“巴士AB 500 ”
“新闻 CA ”
“新闻 CA BLAH”

我的计划是
一个。将它们标记为单词。
湾。创建一个全局数组令牌
c. 将这些字符串与常见标记进行比较。

正如您所猜测的那样，这无济于事。你能为此建议一个算法吗？我正在用python写这个..

4

4 回答 4

2

200000没那么多，你可以这样

  1. 拆分每个字符串以获得标记，例如 "News CA BLAH" -> ["Blah", "CA", "News"]
  2. 为每个列表长度创建一个字典条目，例如在 ["Blah", "CA", "News"] 的情况下所有组合按顺序
  3. 现在只需遍历 dict 并查看组

示例代码：

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

除非重复单词是您的用例的重要特征，否则我建议使用集合。IE：

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”添加到您的列表中，会发生什么？两组字符串必须合并吗？如果不是，如何拆分字符串列表，为什么？

像这样的问题的一个非常通用的工作流程（如果我理解正确的话）是这样的：

  1. 通过倒排索引/所有对相似性搜索/ Simhashing获取候选对列表
  2. 为每对计算一些距离函数并将它们组合成一个权重
  3. 每个加权对（（a，b），权重）现在代表图中的一条边，您可以通过层次聚类/幂迭代将其聚类到“单词匹配组”中
于 2009-11-13T10:29:02.630 回答