0

假设我们手头有一些参考文本

四零七年前，我们的父辈在这片大陆上创造了一个新的国家，这个国家是在自由中孕育的，并致力于人人生而平等的主张。现在我们正在进行一场伟大的内战，考验那个国家，或者任何一个如此构思和如此奉献的国家，是否能够持久。我们在那场战争的伟大战场上相遇。我们来奉献该领域的一部分，作为那些在这里献出生命以使该国得以生存的人们的最后安息之地。我们应该这样做是完全合适和适当的。但是，在更大的意义上，我们不能奉献，我们不能奉献，我们不能圣化这片土地。在这里奋斗的勇敢者，无论生者还是死者，都将它奉献给了它，远远超出了我们微弱的能力来增加或减少。世界不会注意到，也不会记住我们在这里说的话，但它永远无法忘记他们在这里所做的一切。对我们这些活着的人来说，更确切地说，应该在这里献身于他们在这里战斗的他们迄今为止如此高尚地推进的未完成的工作。更确切地说，我们要在这里献身于摆在我们面前的伟大任务——从这些光荣的死者身上，我们将更加致力于他们为之付出最后全部奉献的事业——我们在此下定决心，这些死者不会已经徒劳地死去——这个国家在上帝的统治下将获得自由的新生——人民的政府、民治的政府、民享的政府不会从地球上消失。

我们会收到该文本的片段，没有空格或标点符号，并且删除、插入和替换了一些字符

ieldasafinalrTstingplaceforwhofoughtheregavetheirliZesthatthatn

使用参考文本，我们可以使用哪些工具（在任何编程语言中）来尝试正确地分隔单词

ield as a final rTsting place for who fought here gave their liZes that that n

不需要纠正错误，只需间隔

4

2 回答 2

1

你遇到了奇怪的问题:)

如果您不能依靠大写来获得提示，只需将所有内容都小写即可。

然后得到一个单词字典。也许只是一个单词表，或者你可以试试Wordnet。

还有一个类似的、正确间隔的材料的语料库。如果合适，请下载Wikipedia dump。你需要清理它并分解成 ngram。3 克可能适合这项任务。或者节省时间并使用 Google 的 ngram 数据。网络 ngrams（付费）或书籍 ngrams（免费）。

设置最大字长上限。假设20个字符。

取你的神秘字符串的第一个字符并在字典中查找它。然后取前 2 个字符并查找它们。继续这样做，直到你达到 20 个。存储你得到的所有匹配，但最长的可能是最好的。通过您的字符串，一次移动起点 1 个字符。

您最终会得到一组有效的单词匹配。

循环遍历这个新数组并将每个值与以下值配对，将其与原始字符串进行比较，以便识别所有可能的不重叠的有效单词组合。您最终可能会得到 1 个或多个输出字符串。

如果您有多个，请将每个输出字符串分成 3 克。然后在您的新 ngram 数据库中查找以查看最常见的组合。

可能还有一些节省时间的技术，例如从停用词开始，在字典中检查它们并结合两边的增量字母，然后先在其中添加空格。

... 或者我把整个问题都考虑得太多了，而且有一个 awk 的班轮，有人会用它来谦卑我:)

于 2012-10-12T22:49:57.533 回答
1

您可以使用编辑距离并找到参考的最小编辑距离子字符串来执行此操作。在此处查看我对类似问题的回答（PHP 实现）：

具有错误字符容差的最长公共子串

使用shortest_edit_substring()上面链接中的函数，您可以在删除除字母（或您想要保留的任何内容：字母、数字等）之外的所有内容后添加它以进行搜索，然后将结果正确映射回原始版本。

// map a stripped down substring back to the original version
function map_substring($haystack_letters,$start,$length,$haystack, $regexp)
{
    $r_haystack = str_split($haystack);
    $r_haystack_letters = $r_haystack;
    foreach($r_haystack as $k => $l) 
    {   
        if (preg_match($regexp,$l))
        {       
            unset($r_haystack_letters[$k]);
        }       
    }   
    $key_map = array_keys($r_haystack_letters);
    $real_start = $key_map[$start];
    $real_end = $key_map[$start+$length-1];
    $real_length = $real_end - $real_start + 1;
    return array($real_start,$real_length);
}

$haystack = 'Four score and seven years ago our fathers brought forth on this continent a new nation, conceived in liberty, and dedicated to the proposition that all men are created equal. Now we are engaged in a great civil war, testing whether that nation, or any nation, so conceived and so dedicated, can long endure. We are met on a great battle-field of that war. We have come to dedicate a portion of that field, as a final resting place for those who here gave their lives that that nation might live. It is altogether fitting and proper that we should do this. But, in a larger sense, we can not dedicate, we can not consecrate, we can not hallow this ground. The brave men, living and dead, who struggled here, have consecrated it, far above our poor power to add or detract. The world will little note, nor long remember what we say here, but it can never forget what they did here. It is for us the living, rather, to be dedicated here to the unfinished work which they who fought here have thus far so nobly advanced. It is rather for us to be here dedicated to the great task remaining before us—that from these honored dead we take increased devotion to that cause for which they gave the last full measure of devotion—that we here highly resolve that these dead shall not have died in vain—that this nation, under God, shall have a new birth of freedom—and that government of the people, by the people, for the people, shall not perish from the earth.';

$needle = 'ieldasafinalrTstingplaceforwhofoughtheregavetheirliZesthatthatn';

// strip out all non-letters
$regexp_to_strip_out = '/[^A-Za-z]/';

$haystack_letters = preg_replace($regexp_to_strip_out,'',$haystack);

list($start,$length) = shortest_edit_substring($needle,$haystack_letters);
list($real_start,$real_length) = map_substring($haystack_letters,$start,$length,$haystack,$regexp_to_strip_out);

printf("Found |%s| in |%s|, matching |%s|\n",substr($haystack,$real_start,$real_length),$haystack,$needle);

这也将进行纠错；实际上做起来比不做要容易。如果您想要比 PHP 更快的东西，最小编辑距离搜索在其他语言中实现起来非常简单。

于 2012-10-16T05:34:54.713 回答