如何在没有嵌套循环的情况下比较列表中的元素？

Question

所以我有一个包含 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 个潜在词。

Answer 1

我认为这个问题的一个重要部分是你如何解释问题描述中的“与字典中其他词的最高相似度”的条款。如果您将其视为与所有其他词的最高相似度总和，则可以比嵌套循环更有效地计算该总和。

与其直接比较所有单词，不如计算每个字母包含多少个不同单词。然后在第二遍中，您可以将共享一个单词的每个字母的其他单词的数量相加，这几乎就是我们想要的相似度之和。我们只需要减去单词与自身的相似度（这是它包含的唯一字母的数量），因为我们只应该与 other 个单词进行比较。

这是一个函数，可以按照单词在其中的相同顺序计算相似度列表：

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]

所以，看起来 2 月与其他月份最相似。为了验证这是否正确计数（假设我假设“与其他词的相似性”对每个词意味着什么），我们可以根据您的相似性函数和嵌套循环（这对短词来说很好用）将其结果与另一个版本进行比较列表）。

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]

下载您应该使用的单词列表后（并且非常轻松 pre-processing 它，例如，将所有内容设为小写），我发现这些是列表中最相似的单词：

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

关系通常是包含完全相同字母的单词集（这并不总是很明显，因为通常有很多重复的字母）。如果您以不同方式预处理单词列表（例如，保持区分大小写，或过滤掉连字符和撇号等 non-letter 个字符），您可能会得到略有不同的结果。

如何在没有嵌套循环的情况下比较列表中的元素？

How do I compare elements in a list without nested loops?

python

algorithm

performance

hpc

large-data