假设您有一个包含10,000个电子邮件地址的列表,并且您希望找到此列表中一些最接近的"邻居" - 定义为与列表中其他电子邮件地址可疑接近的电子邮件地址.
我知道如何计算两个字符串之间的Levenshtein距离(由于这个问题),这将给我一个将一个字符串转换成另一个字符串需要多少操作的分数.
假设我将"可疑地接近另一个电子邮件地址"定义为Levenshtein得分小于N的两个字符串.
除了将每个可能的字符串与列表中的每个其他可能的字符串进行比较之外,是否有更有效的方法来查找分数低于此阈值的字符串对？换句话说,这种类型的问题可以更快地解决O(n^2)吗？
Levenshtein对这个问题的算法选择是不是很差？
string algorithm complexity-theory edit-distance cluster-analysis
考虑2个序列X [1..m]和Y [1..n].记忆算法将在时间O(m*n)内计算LCS.有没有更好的算法来找出LCS时间？我想对角完成的memoization可以给我们O(min(m,n))时间复杂度.