程序员的自我修养
Home » 分类目录 » 算法拾遗

Trie树

0条评论4,019次浏览

前几天与学弟聊到他最近的面试题中有一题需要计算两个字符串的最长公共子字符串。当时想到了KMP算法可能可以解决,但仔细想想可能是个比较复杂的任务。后来在网上看到有不少人说用trie树来解决。然后我就糊涂了,记忆中trie树貌似只能解决最长公共前缀的问题吧。于是复习一遍Trie树。

简介

Trie树百度百科解释如下:又称单词查找树,字典树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。

Trie树的直观结构如图所示:
trie tree

图中红色的点代表此处有字符串在此结束,上图中共有7个字符串:abc、abcd、abd、b、bcd、efg、hij(百科中的图,空白边就算作j好了)。

Trie树的使用场景

  • 字符串检索,词频统计,搜索引擎的热门查询。
  • 字符串最长公共前缀。
  • 字符串排序。
  • 作为其他数据结构和算法的辅助结构,如后缀树,AC自动机等。

至于“计算两个字符串的最长公共子字符串”这样的需求无法采用trie树实现,就算能实现也需要大量的改变。

阅读全文>>

标签:,

Levenshtein距离

0条评论2,361次浏览

Levenshtein距离,又称为编辑距离,或者成为字符串相似度,意思是一个字符串转换为另一个字符串所需要的最小编辑次数。编辑包含:插入、删除和替换三种操作。例如字符串:yurnom和yunum的编辑距离为2,因为需要插入一个r和将u替换为o两次操作。

Levenshtein算法由俄罗斯科学家Vladimir Levenshtein在1965年提出,该算法现在广泛用于DNA匹配、字符串纠错、实体共指等领域。

算法简介

将2个字符串转换为一个矩阵,为了简单起见,采用字符串heqi和hoi。转换后进行初始化,如下所示:

h e q i
0 1 2 3 4
h 1 A
o 2
i 3

其中数字部分为初始化的值,现计算绿色格子A处的值,其算法为:

  1. 若A所对应的两个字符相同,则左上角蓝色格子的值+0,否则+1,结果记为R1
  2. 选取上方和左方紫色格子中较小的值,并+1,结果记为R2
  3. 选取R1和R2中的较小值为绿色格子A处的值

经过计算可以得出A处的值为0,当A处计算完毕后,其右方和下方的值可以接着进行计算了,如此整个矩阵的值将可全部计算出来。最后矩阵右下方红色格子的值即为两个字符串的编辑距离。

至于为何左方和上方的值加1、左上角的值根据不同的情况加0或1的原因(也就是这么算的原理)比较简单,在此不再详述。

阅读全文>>

标签:,
11
profile
  • 文章总数:79篇
  • 评论总数:254条
  • 分类总数:31个
  • 标签总数:44个
  • 运行时间:1193天

大家好,欢迎来到selfup.cn。

这不是一个只谈技术的博客,这里记录我成长的点点滴滴,coding、riding and everthing!

最新评论
  • Anonymous: :arrow: :neutral: :cry:
  • Anonymous: java.io.NotSerializableExcepti on: DStream checkpointing has been enabled but the DStreams with their...
  • wick: HI,请问一下,U,S,V得到后,怎么得到近似矩阵呢(用sp ark java),谢谢。
  • Michael Whitaker: Thank you for this blog, it was very helpful in troubleshooting my own issues. It seems that no...
  • Anonymous: :mad:
  • Anonymous: :???:
  • Anonymous: :mad: :mad: :mad:
  • 洋流: 哥们,我问个问题,你把testOnborrow去掉了。。如果 得到的jedis资源是个不可用的,服务从来都不出问题么?
  • 洋流: 哥们,我问个问题,你把testOnborrow去掉了。。如果 得到的jedis资源是个不可用的,服务从来都不出问题么?
  • Anonymous: :razz: :evil: :grin:
  • 张瑞昌: 有很多,比较常见的是Jacob迭代法,一次迭代O(n^3), 迭代次数不清楚。 如果是手动算的话按照定义求就可以了
  • Anonymous: :mrgreen:
  • lc277: 你好 我想问下一般删除节点要多久,要删除的datanode大概用了 1t,解除授权已经30多小时还没完成,请问是出现什么问题了吗 麻烦告诉下谢谢 qq1844554123
  • Anonymous: 你好 我想问下一般删除节点要多久,要删除的datanode大概用了 1t,解除授权已经30多小时还没完成,请问是出现什么问题了吗
  • Anonymous: :smile: :grin: :eek:
  • 李雪璇: 想要完整代码,可以帮忙发给我吗
  • Anonymous: 请问一下,那个 user的推荐结果楼主查看了么? 为什么输入数据 最高是五分,输出结果都是7分8分啥的?怎么设置输出的分数的最 大值?
  • Anonymous: 那个 user的推荐结果楼主查看了么? 为什么输入数据 最高是五分,输出结果都是7分8分啥的?
  • Anonymous: stopGracefullyOnShutdown在yarn- client模式下我测试的无效,你的呢
  • Anonymous: 另外,import的lib包能否发个列表.