通过任意映射在列表中查找等价词

Question

假设您有一个单词列表：

['cat', 'ant', 'bro', 'gro']

使用我们自己构建的一些任意映射{'c'=>'a', 'a'=>'n', 't'=>'t' }，我们可以将'cat'映射到'ant'，同样我们可以找到一些任意映射将'bro'转换为'gro'.

这就是寻找等价词的想法。我写了一个比较两个词的函数，并通过我动态构建的映射检查它们是否等价：

def compareWords(w1, w2):
   mapping = {}
   for i in xrange(0, len(w1)):
       if w1[i] in map:
           if mapping[w1[i]] == w2[i]:
               continue
           else:
               return False
        else:
           mapping[w1[i]] = w2[i]

    return True

示例输入：

['cat', 'ant', 'bro', 'gro']

示例输出：

[['cat','ant'], ['bro', 'gro']]

对列表中的每对单词使用此函数 return 等效单词列表的输出列表在 O(n^2) 中运行，因为每对单词都需要进行比较。我还没有实现这部分，我在输入列表上使用上面的这个方法并生成输出列表，因为这个方法不是我正在寻找的有效比较。有没有办法在 O(n) 时间内找到这个输入列表中的等价词？

进一步说明： 如果我有一个单词列表，并且我想找到所有 "equivalent" 个单词，我需要成对地进行检查。如果我正在比较的单词的所有字母都是唯一的，那么列表中的另一个单词只有在第二个单词中的所有字母也是唯一的情况下才等同于第一个单词。所以 abc 可以映射到 xyz 如果 xyz 在列表中。如果 xyz 在列表中，则 xyz 可以映射到 pqr。鉴于此，abc、xyz 和 pqr 都是等价的。这就是我要找的分组。

Answer 1

如果我没理解错的话，您正在寻找一种方法来检查以对列表形式给出的任意关系 x,y 是否是一个函数，即 x1==x2 意味着 y1==y2。这可以通过集合轻松完成：

def is_function(rel):
    return len(set(rel)) == len(set(x for x, y in rel))


print is_function(['ab', 'cd', 'xd']) # yes
print is_function(['ab', 'cd', 'ad']) # no

如果字母与字母之间的关系是一个函数，那么就您的问题而言，两个单词 "equivalent"：

def equivalent(a, b):
    return is_function(zip(a, b))

print equivalent('foo', 'baa') # yes
print equivalent('foo', 'bar') # no

如果您将不同词之间的等值视为不同的关系，则无法避免逐一比较。此外，您的 "equivalence" 甚至不是可交换的，A ~ B 并不意味着 B ~ A（例如 abc ~ xyx，但 xyx !~ abc）。

根据您的评论，您的关系原来是双射的（注意：您的代码对于这种情况不正确）。将列表拆分为 "equivalence classes" 的最简单（不一定是最有效的）方法是为每个单词计算一个 "hash"，用数字替换字母，其中 0 代表第一个字母，1 代表第二等：

def eq_hash(word):
    return tuple(word.index(c) for c in word)

print eq_hash('mom') # 0 1 0
print eq_hash('dad') # 0 1 0

现在，您可以将具有相同 "hash" 的所有单词组合在一起。这些在您的问题的上下文中是等效的：

group = {}

words = ['mom', 'dad', 'aaa', 'bob', 'ccc', 'xyz', 'abc']

for w in words:
    h = eq_hash(w)
    group[h] = group.get(h, []) + [w]

print group.values()
# [['xyz', 'abc'], ['mom', 'dad', 'bob'], ['aaa', 'ccc']]

Answer 2

如果我理解你的要求，你想对单词进行分组，使每个关系都可以是唯一的，但不一定是唯一的。使用您的示例，mom ~ dad ~ bab，但是 bad 不可能存在于该集合中，因为没有可以从 mom 到 dad (m->d, o->a) 或 dad 到 bab (d->b, a->a) 可以映射到 bad（对于妈妈，m->b 和 d？对于爸爸，d 到 b 一次并跳过下一个？）。

假设您的分组确实是可交换的，那么一旦您对单词进行了分组，您就永远不必重新访问它，除了检查每组的第一个单词。

因此，您首先要将第一个词添加到第一组中。然后，对于每个额外的单词，您需要将其与每个现有组中的第一个单词进行比较——如果匹配，则将其添加到组中；否则，将其添加到组中。如果它不匹配任何组，则将其添加到自己的新组中。

在最坏的情况下，这是 O(N**2)，如果你的集合中的每个单词都属于它自己的组。在最好的情况下，如果你的集合中的所有单词最终都在第一组中，那将是 O(N)，因为你只会将唯一组中的第一个单词与每个其他单词进行比较。如果集合的分布为 log(N)，则该算法实际上是 O(N log(N))。因此，这取决于您的输入集，但与检查每一对相比，它会导致更少的比较。

通过任意映射在列表中查找等价词

Find equivalent words in a list through arbitrary mapping

python

algorithm

string-matching

words

equivalence