標記類似句子的時間複雜度低於n^2

這是我的第一篇文章，長期以來一直是潛伏者，所以我會盡力在這裏解釋一下自己。標記類似句子的時間複雜度低於n^2

我一直在使用最低公共子字符串方法以及基本詞匹配和子字符串匹配（regexp）來聚類網上的相似故事。但問題是它的時間複雜度是n^2（我將每個標題與所有其他標題進行比較）。我已經做了非常基本的優化，比如存儲和跳過所有匹配的標題。

我想要的是對文本塊進行某種預處理，以便每次迭代減少與之匹配的帖子數量。任何進一步的優化也是受歡迎的。

下面是我用於相同的功能。調用它們的主函數首先調用word_match，如果超過70％的單詞匹配，我進一步下去並調用'substring_match'和LCSubstr_len。該代碼是在Python，我可以使用C以及

import re 

def substring_match(a,b): 
    try: 
     c = re.match(a,b) 
     return c if c else True if re.match(b,a) else False 
    except: 
     return False 

def LCSubstr_len(S, T): 
    m = len(S); n = len(T) 
    L = [[0] * (n+1) for i in xrange(m+1)] 
    lcs = 0 
    for i in xrange(m): 
    for j in xrange(n): 
     if S[i] == T[j]: 
      L[i+1][j+1] = L[i][j] + 1 
      lcs = max(lcs, L[i+1][j+1]) 
     else: 
      L[i+1][j+1] = max(L[i+1][j], L[i][j+1]) 
    return lcs/((float(m+n)/2)) 

def word_match(str1,str2): 
    matched = 0 
    try: 
     str1,str2 = str(str1),str(str2) 
     assert isinstance(str1,str) 
    except: 
     return 0.0 
    words1 = str1.split(None) 
    words2 = str2.split(None) 
    for i in words1: 
     for j in words2: 
      if i.strip() ==j.strip(): 
       matched +=1 
    len1 = len(words1) 
    len2 = len(words2) 
    perc_match = float(matched)/float((len1+len2)/2) 
    return perc_match

來源

2010-09-01 Rafi

使用倒排索引：對於每個單詞，存儲對（的docId，numOccurences）的列表。然後，要查找可能與給定字符串相似的所有字符串，請遍歷它的單詞並在倒排索引中查找包含該單詞的字符串。通過這種方式，您將得到一個表（「docId，wordMatchScore）」，該表只會自動包含wordMatchScore不爲零的條目。

有很多可能的優化;同樣，你的代碼是非常不理想的，但是如果我們正在談論減少用於比較的字符串對的數量，就是這樣。

來源

2010-09-01 17:14:15 jkff

感謝您的答覆.. 。你也可以告訴我應該用什麼來創建倒排索引（在python中使用lucene（pylucene）或字典）。我的數據大小可能會增加到最多500k個帖子。 BTW真棒建議，謝謝。我將重寫word_match，並將擺脫子串匹配。 – Rafi 2010-09-01 19:41:41

不，你不需要lucene（直到你的數據實際增加到50萬個帖子，在這一點上我的建議根本沒有幫助）。只需使用簡單的字典。 – jkff 2010-09-01 20:37:15

加快word_match很容易與集：

def word_match(str1,str2): 
    # .split() splits on all whitespace, you dont needs .strip() after 
    words1 = set(str1.split()) 
    words2 = set(str2.split()) 
    common_words = words1 & words2 
    return 2.0*len(common_words)/(len(words1)+len(words2))

這也表明， 'AAA' 和 'A' 有共同的100％，通過這一措施...

來源

2010-09-01 17:26:27

標記類似句子的時間複雜度低於n^2

回答

相關問題