在一串随机字母中插入字符但保持成为单词的可能性，没有庞大的数据结构是否可能？

Question

我有一个按字母顺序排列的 dictionary（大约 20 万个单词）。我只需要知道 string 个字母在字符串中的任何位置插入 char 个字符后是否仍然可以变成单词。换句话说：我需要知道在单词的特定位置插入的哪些字符仍然可以在以后将其变成一个带有插入的单词。应保持字符串中字母的顺序（前后顺序）。

我只是认为如果不使用一些巨大的数据结构或放弃准确性，下降性能（不到半秒）是不可能的。但是，即使您会牺牲准确性，我也不知道有什么好方法可以以非常高的精度（几乎所有可能的正确率确实是可能的）给我提供良好的准确性，同时又能保持一定的平衡。我想知道其他人是否看到了一种方法。以下是我认为必要的：

访问 dictionary 中的每个单词以获得 100% 的准确度和精确度，或者在速度与准确度和精确度之间做出折衷。
检查您访问的单词是否具有 char 正确顺序的字符以匹配字符串。
检查是否有额外的字母适合这个词

有谁知道如何在速度和准确性之间取得良好的结合？现在我有一个数据结构可以非常快地找出某个词是否是一个词，所以我想作为最后的手段，只用随机位置的随机字母查询数据库，然后询问数据结构它是否仍然可以成为一个词，但这感觉像是一种不平衡的方式，没有恒定的时间。

Answer 1

这个问题的措辞方式，几乎就像你在建议答案应该包括一个概率解决方案，例如 Bloom 过滤器，如果不是那么多的话。

但是，我认为考虑到值得尝试实施和优化的要求（少于 0.5 秒，合理的内存使用）而不是满足于不完美的概率解决方案，确定性解决方案是足够可行的。

假设您有一个字符串，并且您想要找到所有可能的单个字符插入到该字符串中，这些字符串产生的字符串可以通过进一步的字符插入变成有效的单词，那么如果该字符串的长度为 n 个字符那么有 n+1 个可能的插入位置和可以在每个位置插入 26 个可能的字符（假设没有重音的英文字母），因此对于 9 个字符长度的字符串将有 260 个可能的插入。对于其中的每一个，您都需要检查它们是否是有效的单词，或者是否可以通过进一步的插入变成有效的单词。乘以字典中的 20 万个条目，转化为 5200 万个测试，每个测试由 "does this string of characters occur in this dictionary entry, in this order" 组成。如果我们能找到一种方法来 "early out" 大多数测试，这似乎可以在现代台式机或智能手机上实现。

在伪代码中，基本算法是：

List findPossibleInsertions(String currentString)
{
    List list = {};
    for(int pos = 0; pos < currentString.length + 1; pos++)
    {
        for(char c = 'a'; c <= 'z'; c++)
        {
            String insertedString = insert c into currentString before pos;
            if(stringIsImpossible(insertedString))
                continue;   // high level test whether the string could be turned into a valid word

            int64 stringMask = computeStringMask(insertedString);

            // the string is not impossible according to the test, but we need to verify that it is actually possible:
            for(String s in Dictionary)
            {
                // check if the string could be turned into s via insertions using a simple mask check to potentially exclude it (but not 100% confirm it):
                if((s.mask & stringMask) != stringMask)
                    continue;   // it's not possible to turn insertedString into s via insertions

                if(s.length < insertedString.length)
                    continue; // can't insert chars to make a shorter string

                // confirm that is it possible:
                if(canMakeStringViaInsertions(insertedString, s)
                {
                    list.add(insertedString); // this is a valid insertion, add to the list
                    break;
                }
            }
        }
    }
}

这给我们留下了 3 个任务

查找高级检查以确保给定的字符串不可能用于创建具有进一步插入的任何有效单词
计算一个掩码，该掩码可用于测试是否可以扩展给定字符串以通过插入创建给定世界，允许误报但不允许漏报
确定地测试给定的字符串是否可以通过插入来扩展以创建给定的单词，不允许误报或漏报

对于第一个任务，我们可以使用预先计算的位掩码来存储某些字符序列是否可以出现在有效单词中（有可能在它们之间添加额外的字符）。要存储 5 个字符的序列，我们需要 26*26*26*26*26 = 11881376 位，或 1485172 字节。鉴于这将大致等于存储 200K 单词所需的存储量（假设平均单词长度为 5.1 个字符，加上一个终止空值，再加上每个单词的 4 字节偏移量），我认为这不算数作为 "enormous".

为 3 个字符、4 个字符和 5 个字符的每个组合存储一个位域。

将位域设置为全零，然后遍历字典。以 5 个字符为例，对于每个单词，采用每个可能的 5 个字符序列，其中序列中的每个字符出现在单词序列中的前一个字符之前。例如，单词 "pencil" 给出以下 5 个字符序列：

"encil"
"pncil"
"pecil"
"penil"
"pencl"
"penci"

使用以下公式将这些 5 个字符的组合中的每一个添加到位域：

index = ((s[0]-'a')*(26^4)) + ((s[1]-'a')*(26^3)) + ((s[2]-'a')*(26^2)) + ((s[3]-'a')*26) + (s[4]-'a');
bitfield[index] = 1;

如果将字典中所有单词的所有可能的 5 字符序列添加到位域，则意味着如果 5 字符序列出现在字符串中但未在位域中设置其位，这意味着不可能通过向字符串中插入字符来在字典中创建任何单词，因为字典中没有按该顺序出现的这 5 个字符的条目。因此，无论您添加什么字符，都不会产生有效的单词。

可以对 4 个字符和 3 个字符的位域重复相同的过程。

要检查字符串是否可以使用位域扩展为字典中的有效单词，请使用如下函数：

boolean stringIsImpossible(String s)
{
    // test against 5 char bitfield:
    for(i = 0; i <= s.length - 5; i++)
    {
        index = ((s[i]-'a')*(26^4)) + ((s[i+1]-'a')*(26^3)) + ((s[i+2]-'a')*(26^2)) + ((s[i+3]-'a')*26) + (s[i+4]-'a');
        if(5charBitmask[index] == 0)
            return true;
    }
    if(s.length > 4)
        return false;
    // test against 4 char bitfield:
    for(i = 0; i <= s.length - 4; i++)
    {
        index = ((s[i]-'a')*(26^3)) + ((s[i+1]-'a')*(26^2)) + ((s[i+2]-'a')*26) + (s[i+3]-'a');
        if(4charBitmask[index] == 0)
            return true;
    }
    if(s.length > 3)
        return false;
    // test against 3 char bitfield:
    for(i = 0; i <= s.length - 3; i++)
    {
        index = ((s[i]-'a')*(26^2)) + ((s[i+1]-'a')*26) + (s[i+2]-'a');
        if(3charBitmask[index] == 0)
            return true;
    }
    return false;
}

对于第二个任务，有必要为每个字典单词创建一个位掩码，可以很容易地用于测试是否可以通过添加字母从现有单词字符串创建。这意味着它需要以相同的顺序包含字符串中的所有字母。从逻辑上讲，如果它不包含字符串中的所有字母，那么它不能既包含字符串中的所有字母又以相同的顺序包含它们。因此，我们可以创建一个位掩码，如果单词包含字母 'a'，则将位 0 设置为 1，如果包含 'b'，则设置位 1，如果包含 'c'，则设置位 2，等等。然后如果我们将字符串的位掩码与我们试图查看的单词的位掩码进行 AND 运算，看看是否可以通过将字符插入字符串来生成，如果结果不等于字符串的位掩码，则无法从中生成单词，因为并非字符串中的所有字母都出现在字典单词中。

此外，我们可以根据某些字母是否出现在某些其他字母之后，在掩码中设置额外的位。例如，如果字符串中有一个字母 'g'，我们可以设置一个位，然后在某个时候有一个字母 't'。如果该位在字符串中设置但未在目标词中设置，则无法从字符串中生成该词。也可以重用位来处理多个字母组合。例如，如果 'g' 后跟 't'，或者 'd' 后跟 'j' 等，则可以设置一个位。冲突的可能性是减少是因为在 'g' 后跟 't' 的情况下，'g' 和 't' 位将被设置，因此匹配带有 [=72 的单词=] 后跟 'j'，共享位可能会发生冲突，但很可能不会设置单独的 'd' 和 'j' 位。只要没有假阴性，有一些假阳性是可以接受的。

计算字符串掩码的函数大致如下：

int64 computeStringMask(String s)
{
    int64 mask = 0;
    // add individual letters to bitmask:
    for(int i = 0; i < s.length; i++)
    {
        mask |= 1 << (s[i]-'a');
    }
    // add "followed by" letter combinations to bitmask:
    for(int i = 0; i < s.length-1; i++)
    {
        for(int j = i+1; j < s.length; j++)
        {
            mask |= 1 << (((((s[i]-'a') * 26) + (s[j]-'a')) % 37) + 26);
        }
    }
    return mask;
}

需要为字典中的每个字符串计算和存储此掩码。

第三个任务：测试是否可以扩展给定的字符串来创建给定的单词，只需检查该单词是否以正确的顺序包含字符串中的每个字符：

boolean canMakeStringViaInsertions(s, word)
{
    int i = 0; j = 0;
    while(word[j] != 0)
    {
        if(s[i] == word[j])
        {
            // match!
            i++;
            if(s[i] == 0)
                return true;   // all chars have matched
        }
        j++;
    }
    return false;
}

对findPossibleInsertions()函数的进一步优化是将字典分成块，并为块中的每个单词计算字符串掩码并将它们一起进行或运算。如果从字符串计算出的掩码对块掩码的测试结果为阴性，则需要测试块中的 none 个单词。

在一串随机字母中插入字符但保持成为单词的可能性，没有庞大的数据结构是否可能？

Insert character inside a string of random letters but maintain possibility to become word, is it possible without immense data-structure?

java

string

search

insert

character