文本比较算法Ⅴ——回顾贴，对前面几篇文章的回顾与质疑
文本比较算法Ⅰ——LD算法 文本比较算法Ⅱ——Needleman/Wunsch算法 文本比较算法Ⅲ——计算文本的相似度 文本比较算法Ⅳ——Nakatsu算法 在写了本系列的前面几篇文章之后。有些网友质疑文章的正确性。在仔细的推敲之下，这些网友指正的不无道理。下面举一个反例，来质疑前面...
文本比较算法Ⅲ——计算文本的相似度
在“文本比较算法Ⅰ——LD算法”中，介绍了编辑距离的计算。 在“文本比较算法Ⅱ——Needleman/Wunsch算法”中，介绍了最长公共子串的计算。 在给定的字符串A和字符串B，LD(A,B)表示编辑距离，LCS(A,B)表示最长公共子串的长度。 如何来度量它们之间的相似度呢？ 不...
文本比较算法Ⅸ——Primal-Dual算法
研究文本比较算法有一段时间。看到Primal-Dual算法，作为不同的求LCS算法，介绍如下。 原文在《An almost-linear time and linear space algorithm for the longest common subsequence problem》 &n...
文本比较算法Ⅷ——再议Nakatsu算法
研究文本比较算法已经一段时间了。把思路重新理了理。 在“文本比较算法Ⅳ——Nakatsu算法”中提到“对角线上的数字就是最长公共子序列的下标”。 在“文本比较算法Ⅶ——线性空间求最长公共子序列的Nakatsu算法”中提到“每行最左边不为V的数字就是最长公共子序列的下标”。 以上两个结论，...
文本比较算法Ⅶ——线性空间求最长公共子序列的Nakatsu算法
在参阅《A Longest Common Subsequence Algorithm Suitable for Similar Text Strings》（Narao Nakatsu，Yahiko Kambayashi，Shuzo Yajima著）后。发现该算法可以利用线性空间求出最长公共子序列。该...
文本比较算法Ⅳ——Nakatsu算法
在“文本比较算法Ⅰ——LD算法”、“文本比较算法Ⅱ——Needleman/Wunsch算法”中介绍的LD算法和LCS算法都是基于动态规划的。它们的时间复杂度O(MN)、空间复杂度O(MN)（在基于计算匹配字符串情况下，是不可优化的。如果只是计算LD和LCS，空间占用可以优化到O(M)）。 Na...
文本比较算法Ⅵ——用线性空间计算最大公共子序列（翻译贴）
研究文本比较算法有一段时间了。近日研读了《A Linear Space Algorithm for Computing Maximal Common Subsequences》（D.S.Hirschberg著）。文章写于1975年。很多其他的论文都会引用这篇论文，可见这篇论文的质量。同时，该文作者D...
文本比较算法Ⅱ——Needleman/Wunsch算法
在“文本比较算法Ⅰ——LD算法”中介绍了基于编辑距离的文本比较算法——LD算法。 本文介绍基于最长公共子串的文本比较算法——Needleman/Wunsch算法。 还是以实例说明：字符串A=kitten，字符串B=sitting 那他们的最长公共子串为ittn（注：最长公共子串不需要连...
文本比较算法Ⅰ——LD算法
在日常应用中，文本比较是一个比较常见的问题。文本比较算法也是一个老生常谈的话题。 文本比较的核心就是比较两个给定的文本（可以是字节流等）之间的差异。目前，主流的比较文本之间的差异主要有两大类。一类是基于编辑距离（Edit Distance）的，例如LD算法。一类是基于最长公共子串的（Long...
本页面内关键词为智能算法引擎基于机器学习所生成，如有任何问题，可在页面下方点击"联系我们"与我们沟通。
