根據公共性對字符串數組進行分類

我有很多字符串（多字）的列表（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

根據公共性對字符串數組進行分類

回答

相關問題