代码之家 › 专栏 › 技术社区 › Jedidja

我可以使用什么算法来确定两个文档中是否有N个单词的序列?

sequence comparison language-agnostic string

2

Jedidja · 技术社区 · 15 年前

给出两份文件:

现在是 我们不满的冬天在约克太阳的照耀下创造了灿烂的夏天; 以及我们家里所有的云深埋在海洋深处。现在,我们的眉毛上系着胜利的花环; 我们瘀伤的手臂挂在纪念碑上; 我们的尾部阿拉姆变成了欢乐的会议, 我们以令人愉快的方式行进。

(理查德三世)

理查德(约克公爵):(把酒杯敲在桌子上三下)安静! 安静!为了国王!

金(理查德三世):[站着,弓着腰,说话笨拙] 现在是 我们甜蜜的夏天, [自制的?[呃?]-在都铎云中铸就冬天。

(黑爵士,第一季,第一集)

有人能用什么样的算法来找出两个文档中都存在哪些3字序列?当然,如果有的话,这是不保证的。

在本例中, 现在是 “是两个文档中唯一出现的3字序列。

2 回复 | 直到 15 年前

1

2

Nabb 15 年前

除了暴力,最简单的解决方案是制作一个哈希图,为一个文本的每个单词元组输入条目,然后检查另一个文本中的每个元组是否存在于哈希图中。如果给定一个恒定的窗口(3个字),这将是线性的,但是我们可以在线性时间内做到这一点,而不受窗口大小的影响。

为了有效地做到这一点,我们使用 rolling hash . 滚动哈希的输入字符将是单词的哈希。这种技术被称为 Rabin-Karp algorithm .

2

Steve Jessop 15 年前

听起来您在寻找长度为3的常见子串,除了“字符串”由“字符”组成,实际上是单词,而不是单个字符。所以,“我有一个狡猾的计划”是一个长度为5的字符串。

后缀树通常在这里提到: http://en.wikipedia.org/wiki/Generalised_suffix_tree 但是,你是否需要这取决于你的文本有多长。从每对单词边界(每个字符串一个)开始进行比较的两个嵌套循环将最终完成该任务。