首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >我可以使用什么算法来确定在两个文档中是否出现n个单词序列?

问我可以使用什么算法来确定在两个文档中是否出现n个单词序列?
EN

Stack Overflow用户
提问于 2010-11-25 14:46:53
回答 2查看 128关注 0票数 2

给出两份文件:

现在是我们不满的冬天,这是由约克的太阳创造的灿烂的夏天;所有的云彩在我们的房子里,在深深的海洋的怀抱中被掩埋。现在,我们的眉毛被胜利的花环捆住了;我们被瘀伤的手臂挂在纪念碑上;我们的严厉通知变成了欢快的会议;我们可怕的游行变成了令人愉快的措施。

(理查三世)

理查德(约克公爵):把他的酒杯三次敲在桌子上,安静!安静!为了国王! 国王(理查德三世):站着,驼背,现在尴尬地说着,是我们甜蜜内容的夏天,由这些都铎云铸成的冬天。

(BlackAdder,第一季,第1集)

谁能用哪种算法来找出两个文档中都存在哪一个三字序列?当然,如果有的话--这是不确定的。

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

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2010-11-26 15:42:35

如果没有蛮力,最简单的解决方案是创建一个散列图,其中包含一个文本的每个元组的条目,然后检查另一个文本中的每个元组是否存在于散列图中。这将是线性的,给定一个恒定的窗口(3字),但是我们可以在线性时间内做到这一点,而与窗口大小无关。

为了有效地完成这个任务,我们使用了一个滚动散列。滚动散列的输入字符将是单词的散列。这种技术被称为Rabin-Karp算法。

票数 2
EN

Stack Overflow用户

发布于 2010-11-25 14:55:07

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

后缀树通常在这里被提到:树,但是您是否需要这一点取决于您的文本的长度。两个嵌套循环来比较,从每对单词边界开始(每个字符串一个),最终将完成任务。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/4278279

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档