1

我正在尝试将给定字符串与列表的差异进行比较。确切地说，我正在尝试将给定的单词（如果该单词的一个字母不同）与我的单词列表进行比较。

list = ['fake','bake','sake','rake'] #probably a set

如果给定的词是take那么结果将返回fake bake sake rake

如果这个词是bare那么返回是bake

我打算这样做的方式是将给定的单词拆分为并启动一个循环，以将该单词的每个字母与字典列表（a，b，c）互换。在我的循环的每次迭代中，我计划检查这个词是否在我的词表中。

我只计算了一个 4 个字母的单词，我必须做大约 26^4 个循环才能检查每个字母组合以匹配我的单词列表。

有人可以告诉我一种检查单词组合的有效方法吗？

4

5 回答 5

1

水母库可以计算单词之间的大量距离。使用这个轮子可能比自己发明一个更好。

从示例页面：

>>> import jellyfish
>>> jellyfish.levenshtein_distance('jellyfish', 'smellyfish')
2
>>> jellyfish.jaro_distance('jellyfish', 'smellyfish')
0.89629629629629637
>>> jellyfish.damerau_levenshtein_distance('jellyfish', 'jellyfihs')
1

所以适用于你的问题：

import jellyfish
target = 'take'
list = ['teak','fake','bake','sake','rake','sale']
outlist = [x for x in list if jellyfish.levenshtein_distance(x,target) == 1]

print outlist
['fake', 'bake', 'sake', 'rake']
于 2013-10-08T22:36:12.313 回答
0

尝试针对每个基本单词逐个字母地测试该单词。在发现的每个差异上增加一个计数器，并跟踪具有 0 或 1 差异的单词。这在基本词的数量上是线性的，比您的指数方法要好得多。

这是一个参考实现：

def atMostOneDifference(word):
    matching = []
    for baseWord in ['fake','bake','sake','rake']:
        distance = 0
        if len(word) != len(baseWord):
            continue
        # We take the i-th letter from word and baseWord...
        for letter, baseLetter in zip(word, baseWord):
            if letter != baseLetter:
                distance += 1
        if distance <= 1:
            matching.append(baseWord)
    return matching
于 2013-10-08T22:30:22.567 回答
0 
word = 'take'
matches = []
candidate_list = ['fake','bake','sake','rake']
for candidate in candidate_list:
    differences = 0
    for (original_word_letter, candidate_word_letter) in izip(word, candidate):
        if original_word_letter != candidate_word_letter:
            differences += 1
        if differences > 1:
            break
    else:
        matches.append(candidate)

这在 for 循环中使用了相对晦涩的else子句，如果由于 a 退出循环，则不会执行该子句break，并假设字长都是相等的 - 测试不相等的长度当然很简单。

使用内置名称（如list您自己的变量）是一个坏主意 - 它们没有提供信息，它们会将内置含义隐藏在适当的范围内。

于 2013-10-08T22:30:29.980 回答
0

我自己喜欢切片。使用返回 True/False 的函数来过滤列表中您需要/想要的条件。

orig = 'abcdef#ghijklmn'
test = 'abcdef%ghijklmn'
test_bad = 'abcdef%ghijk*mn'

def one_letter_different(s1, s2):
    """returns True if there is only one letter different between s1 and s2.

    Sequentially check each letter of each string till they don't match
    then check to see if the rest of the strings are equal.

    s1, s2 -> str
    """
    for i, c in enumerate(s1):
        if c != s2[i]:
            # test for substituition, deletion and insertion
            return (s1[i + 1:] == s2[i + 1:] or
                    s1[i:] == s2[i + 1:] or
                    s1[i+1:] == s2[i:])
    # s1 equals s2
    return False

print one_letter_different(orig, test)
print one_letter_different(orig, test_bad)

test = 'take'
print [item for item in ['fake','bake','sake','rake']
       if one_letter_different(item, test)]

test = 'bare'
print [item for item in ['fake','bake','sake','rake']
       if one_letter_different(item, test)]

产生：

>>> 
True
False
['fake', 'bake', 'sake', 'rake']
['bake']
>>>

比较函数也可以定义为：

from operator import ne
from itertools import izip_longest

def one_letter_different(s1, s2):
    """returns True if there is less than two letters different.

    Sequentially compare the letters of each string and sum the differences.

    s1, s2 -> str
    """
    return sum(ne(*thing) for thing in izip_longest(s1, s2, fillvalue = None)) == 1
于 2013-10-08T23:03:13.667 回答
0

这是一个简单的表达式，它返回不同字母的数量或False字符串是否具有不同的长度：

len(s1) == len(s2) and sum(1 for a, b in zip(s1, s2) if a != b)

在你的情况下：

target = 'take'
list = ['fake','bake','sake','rake']

def diff(s1, s2): 
    return len(s1) == len(s2) and sum(1 for a, b in zip(s1, s2) if a != b)

print [word for word in list if diff(word, target) == 1]
于 2013-10-08T23:36:12.310 回答