5

我正在尝试找到一种方法来查找连续出现的加扰文本中的特定单词。未找到的字符将有一个X到位。

例如，假设字典单词列表是：

jane
john
brownbag
foo
youth

和乱码：

ofozlhuoyt => fooXXyouth
yuawbnrobgajen => XXbrownbagjane
janjeohn => (nothing since jane and john aren't consecutive)

我正在尝试的方法：

说，我有一个带有键的散列，a其中z设置为每个键的值。集合中的每个数字将表示包含特定字符的单词的索引。

从上面的例子：

{a: [0,2]}
{b: [2]}
{c: []}
{e: [0]}
{f: [3]}
{g: [2]}
{h: [1,4]}
{j: [0,1]}
...
{n: [0,1,2]}
{o: [1,2,3,4]}
{r: [2]}
{u: [4]}
{t: [4]}
{w: [2]}
{y: [4]}
...
{z: []}

准备好上述内容后，我们可以开始查看加扰文本的每个字符：

第一个字符串：ofozlhuoyt

  1. o => 存在于 1、2、3 和 4 中

  2. 从 1 开始：简（长度 4）

  3. 得到 4 个字符：ofoz

  4. "jane".sort(false) == "ofoz".sort(false)?

  5. 如果为假：对 2 重复步骤 1 到 3 (john)

  6. 如果为真：将 foo 添加到好词列表中，并从第 0 步开始z

有没有更好的方法来做到这一点？我觉得存在更好的数据结构来解决这样的问题，但我不知道该使用哪个..

4

3 回答 3

3

你可以使用素数！

当您将 n 个素数相乘时，您得到的乘积将不同于任何其他素数组合。

在您的问题中，关键是顺序无关紧要，因此排序将浪费时间。换句话说，

'jane' == 'ejna' == 'jnea' == ...

因此，您可以基于酷素数属性创建自己的哈希函数，并使用可交换性而不是乘法来完全避免排序/字符串搜索。而在python中，你甚至不必担心整数的大小；如果您的字典有很大的单词，这将派上用场。

下面是一个简单的 dict 将字母映射到前 26 个素数，以及随附的哈希函数。

letters_to_primes = {'a': 2, 'b': 3, 'c': 5, 'd': 7, ... 'x': 89, 'y': 97, 'z': 101}

def my_prime_hash(word):
    sum = 1
    for letter in word:
        sum = sum * letters_to_primes[letter] # Multiplication is commutative!
    return sum

同样，我们在这里利用的关键属性是

my_prime_hash('jane') == my_prime_hash('enaj') == ... == 27434

现在我们只需要创建给定字典单词的字典。我提出了一个外部链接哈希表。让我们称之为“散列词”。

# Given these words
words = ['jane', 'john', 'brownbag', 'foo', 'youth', 'nib', 'bin']

# Compute the hash table
hashed_words = {}
for word in words:
    w_hash = my_prime_hash(word)
    if w_hash in hashed_words: hashed_words[w_hash].append(word)
    else: hashed_words[w_hash] = [word]

运行后， hashed_words 看起来像：

{1113571: ['john'], 27434: ['jane'], 
 28717: ['foo'], 448956643: ['youth'], 
 3131090838L: ['brownbag'], 2967: ['nib', 'bin']}

这就是我们想要的。

现在，您可以通过计算字母的乘积开始对打乱的单词进行散列，并在每个点检查乘积是否在 hashed_words 中。对于像“mrtasgth”中的“mart”和“smart”这样的情况，需要一个像其他人提出的状态机（见下面的评论）。

注意：您可以考虑字典中出现的所有字母的频率分布，并将最低的素数分配给频率最高的字母，而不是按升序分配素数。这确实会在创建“hashed_words”哈希表时节省内存。

于 2013-11-13T06:40:11.537 回答
2

如果您有足够的内存来实现它，那么有一种可能更快的方法。

首先，为每个单词生成所有排列。因此，对于“简”，您将拥有：

aejn
aenj
ajen
ajne
anej
anje
etc.

然后，为Aho-Corasick 算法构建一个状态机，单个单词的每个排列都进入相同的结束状态。该结束状态将输出您要查找的字符串。

现在通过状态机运行文本。输出将是找到的单词及其位置。然后，您可以按位置对找到的单词进行排序，并确定它们是否连续出现。

状态机可能非常大（每个单词有 n! 个状态，其中 n 是单词中的字符数），并且需要一些时间来构建。但是一旦建成，它就会很快匹配。如果您的单词列表是静态的并且您有很多文本要搜索，那么这就是要走的路。前提是你有足够的内存。

我使用了一种改进的 Aho-Corasick 算法，该算法在文本中搜索视频标题中出现的数百万个短语（乐队和歌曲名称）。状态机占用了大约 10 GB 的 RAM，构建起来大约需要一个小时，但在匹配方面它很快。

于 2013-11-13T04:06:21.613 回答
1

也许是这样的：

http://en.wikipedia.org/wiki/Rabin–Karp_algorithm

这与哈希思想非常相似，并且与 aho-corasick 算法有关

于 2013-11-13T08:31:50.187 回答