根据公共性对字符串数组进行分类

我有很多字符串（多字）的列表（200000）。我想根据这些字符串之间的单词匹配的comman数组对这些字符串进行分组。我不能认为较低的计算时间的算法为这个根据公共性对字符串数组进行分类

“AB 500”
“公交AB 500”
“新闻CA”
“新闻CA BLAH”

我的计划是
a。将它们标记为单词。 b。创建全局数组标记
c。将这些字符串与普通令牌进行比较。

正如你猜对此没有帮助。你能为此提出一个算法吗？我正在蟒蛇写这个..

来源

2009-11-12 Ramya

假设三个字符串“新闻CA”，“新闻无论”，“新闻CA无论”，他们如何分组？他们都是“新闻”组的一部分，然后有分组？ – 2009-11-12 04:32:21

这是有点低估。如果输入还包括“Bus AB”，“Bus CD 500”和“Bus AB 201”？哪个组在哪里？ – 2009-11-12 04:33:12

打算根据令牌的数量和令牌的长度来计分 – Ramya 2009-11-16 21:02:20

200000不算多，你能做到这一点

分割每个字符串获得令牌例如“News CA BLAH” - > [“Blah”，“CA”，“News”]
每个列表的长度创建一个字典条目。在以下情况下[“嗒嗒”，“CA”，“新闻报”为了
现在只要环通的字典，看到了团体

示例代码的所有组合：

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-12 04:58:55

你的意思是这样的吗？

>>> 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-12 04:57:51

除非字重复是你的使用情况的一个重要特点，我建议套。 I.e .:

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-12 05:30:10

这将会非常慢，因为OP表示200000字符串，意味着循环4万次 – 2009-11-12 08:28:33

是的，它是'O（n ** 2）'，但是如果它接近OP所期望的，然后它是一个简单的优化基础，包括算法和启发式算法。现在的问题只是有点不确定;-)。 – 2009-11-12 15:55:19

如果将字符串“AB 500 News CA”添加到列表中，会发生什么情况？这两组字符串是否必须合并？如果没有，如何分割字符串列表，为什么？

像这样的问题（如果我理解正确的话）很一般的工作流程是这样的：

通过倒排索引/ All pairs similarity search/Simhashing
计算器一些距离函数获取候选对列表对于每一对并将它们组合成单个权重
每个加权对（（a，b），权重）现在表示图中的边缘，您可以通过分层聚类/力量将其聚类到“词匹配组”中迭代

来源

2009-11-13 10:29:02 ephes

根据公共性对字符串数组进行分类

回答

相关问题