所以我有一個包含 466,550 個單詞的龐大串列，我需要將這些單詞相互比較以檢查它們之間的相似性。在我的例子中，兩個詞之間的相似性被定義為它們之間的共同字符的數量。但如果我嘗試：
for i in words:
for j in words:
if(i!=j):
temp.append(similar(i,j))
sim.append(max(temp))
temp = []
它將運行 466,550^2 次，并且需要很長時間才能獲得最終輸出。那么還有另一種方法可以在線性時間內做同樣的事情嗎？
編輯： Similar 有一個非常基本的定義，如下所示：
def similar(a, b):
x = list(set(a)&set(b))
return len(x)
我查找了一種比較單詞的方法，然后只回傳每次比較的相似字符總數
編輯2：
因此，對于那些感興趣的人來說，這是整個問題：
約翰和比利是兩個好朋友。約翰想破解比利的 Insta 帳戶的密碼只是為了好玩。密碼是這本詞典中的一個英文單詞：
https://raw.githubusercontent.com/dwyl/english-words/master/words.txt。
他不能嘗試字典中的所有單詞，因為每次嘗試至少需要 30 秒。但他知道以下關于密碼的線索。
- 線索1：該詞與詞典中其他詞的相似度最高。兩個詞之間的相似性由共同字符的數量定義。
- 線索2：這個詞中有大量的元音。
- 線索3：這個詞中有大量的字符。創建 3 個獨立的單詞串列，根據每個線索對單詞進行排序。最后根據它們在這 3 個串列中的位置（每條線索的權重為 0.33）對每個單詞進行排名。根據最終排名提出前 100 個潛在單詞。
uj5u.com熱心網友回復：
我認為這個問題的一個重要部分是你如何解釋問題描述中的“與字典中其他單詞的最高相似度”這個子句。如果您認為這意味著與所有其他單詞的最大相似性總和，那么您可以以比嵌套回圈更有效的方式計算該總和。
您可以計算每個字母包含多少個不同的單詞，而不是直接比較所有單詞。然后在第二遍中，您可以將共享每個單詞字母的其他單詞的數量相加，這幾乎是我們想要的相似度總和。我們只需要減去單詞與自身的相似度（即它包含的唯一字母的數量），因為我們只應該與其他單詞進行比較。
這是一個函式，它按照單詞的相同順序計算相似性串列：
from collections import Counter
def compute_similarities(words):
letter_count = Counter()
for word in words: # first pass
letter_count.update(set(word)) # count each letter
similarities = []
for word in words: # second pass
letters = set(word)
similarities.append(sum(letter_count[letter] for letter in letters)
- len(letters)) # correct for self similarity
return similarities
這是一個運行示例，將月份的名稱作為我們的字典：
>>> months = [
"january", "february", "march", "april",
"may", "june", "july", "august",
"september", "october", "november", "december",
]
>>> compute_similarities(months)
[23, 28, 18, 14, 12, 13, 10, 12, 24, 21, 23, 22]
因此，看起來二月與其他月份最相似。為了驗證這是否正確計數（考慮到我對每個單詞“與其他單詞的相似性”的含義的假設），我們可以根據您的相似性函式和嵌套回圈將其結果與另一個版本進行比較（這對于短詞效果很好串列）。
def similar(a, b):
x = list(set(a)&set(b))
return len(x)
def compute_similarities_bruteforce(words):
similarities = []
for i in words:
total = 0
for j in words:
if(i!=j):
total = similar(i,j)
similarities.append(total)
return similarities
測驗運行：
>>> compute_similarities_bruteforce(months)
[23, 28, 18, 14, 12, 13, 10, 12, 24, 21, 23, 22]
在下載了您應該使用的單詞串列（并對其進行了非常輕微的預處理，例如將所有內容設為小寫）后，我發現這些是串列中最相似的單詞：
>>> similarities = compute_similarities(words)
>>> simiarity_sorted_words = sorted(zip(similarities, words), reverse=True)
>>> simiarity_sorted_words[:20]
[(3059877, 'pseudolamellibranchiate'),
(3059877, 'pseudolamellibranchiata'),
(2973121, 'pseudoconglomeration'),
(2966493, 'pseudoanthropological'),
(2956212, 'pseudoromantically'),
(2949584, 'spondylotherapeutics'),
(2949584, 'pseudophilanthropically'),
(2949584, 'pseudohallucinatory'),
(2946269, 'neuropharmacologist'),
(2932039, 'salpingo-oophorectomy'),
(2929360, 'hyperconstitutionalism'),
(2925092, 'encephalomyocarditis'),
(2887146, 'sphygmomanometrically'),
(2887146, 'semianthropologically'),
(2887146, 'oophorosalpingectomy'),
(2884111, 'pseudoconservatively'),
(2880336, 'pneumatico-hydraulic'),
(2875526, 'quasi-complimentary'),
(2874192, 'cloth-measuring'),
(2873602, 'cloth-spreading')]
The ties are generally sets of words that contain exactly the same letters (which aren't always obvious, since there are often quite a lot of duplicated letters). You might get slightly different results if you preprocess the word list differently (e.g. keeping case sensitivity, or filtering out non-letter characters like hyphens and apostrophes).
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/432699.html
上一篇：有效填充2DSciPy稀疏矩陣