根据共同点对字符串数组进行分类

Question

我有一个非常大的字符串列表（有20万个字符串），这些字符串都是由多个单词组成的。我想根据这些字符串中共同的单词来对它们进行分组。不过，我想不出一个计算时间低的算法来实现这个目标。

比如说，以下是一些字符串：
AB 500
"Bus AB 500"
News CA
News CA BLAH

我的计划是：
a. 把这些字符串拆分成单词。
b. 创建一个包含所有单词的全局数组。
c. 用这些共同的单词来比较字符串。

不过，正如你猜的，这样做并没有什么帮助。你能给我推荐一个算法吗？我是在用Python写这个。

Answer 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']

Answer 2

除非你需要重复的词语对你的情况很重要，否则我建议使用集合。也就是说：

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])

这样接近你想要的结果吗？它确实按照你想要的方式对你提供的四个字符串进行了分类，不过这只是一个很简单的例子，所以我再确认一下;-).

Answer 3

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']