string - 如何从乱码中找词

Question

我正在尝试找到一种方法来查找连续出现的乱序文本中的特定单词。未找到的字符将有一个 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开头:jane(长度为4)

3. 获取 4 个字符:ofoz

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

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

6. 如果为真:将 foo 添加到好词列表中并从 z

   开始步骤 0

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

Answer 1

你可以使用素数!

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

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

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

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

下面是一个简单的字典，将字母映射到前 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

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

# 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”哈希表时节省内存。