0

是否有 O(n) 或更快的算法用于按 levenshtein 距离对列表进行排序？我看过一些关于 SO 的解决方案，但它们都调用了传统的排序。现在，假设您只是对输入的字节求和：您将获得几乎按它们的 levenshtein 距离排序的散列键。例如，我采用一组随机字符串并通过字节求和计算它们的哈希值：

[ { hash: 2826, val: 'LKAMFKLFUAHUHAUHAUHAU:ANGONEGANAILFJAL:' },
  { hash: 2829, val: 'LKAMFKLFLFUAHUAHUHAUAHANGONEGANAILFJAL:' },
  { hash: 2845, val: 'LKAMFKLFLFAKAKKAKAfiO:ANGONEGANAILFJAL:' },
  { hash: 3064, val: 'LKAMFKLFKKKlaNflanfiO:ANGONEGANAILFJAL:' },
  { hash: 3092, val: 'LKAMFKLFLFklaNflanfiO:ANGONEGANAILFJAL:' },
  { hash: 3203, val: 'LKAMFKLFLFklaNflanfiRSRSRSRSRRNAILFJAL:' },
  { hash: 3249, val: 'LKNFUU{N{UAFN{NF}FNPNF{FN{APNF{WNFF{NF' },
  { hash: 3843, val: 'ddddddddddaaaaaaaaaddddddddddaaaaaaaaaa' },
  { hash: 3858, val: 'safndjnjcmxn,znv,mnm,n,mvnm,vn,mznv,mvv' },
  { hash: 3934, val: 'nngnangngdsgsangnanwns.mnv.nv.xnjvnsf.,' },
  { hash: 3972, val: 'adadsadadsadadadsadsadadsadsadadsadsada' },
  { hash: 3992, val: 'adsadadadsadasdasdafadfasfdsafsafasfafd' },
  { hash: 4041, val: 'asfdsafasdfsafafasdfasdfafsdfdasfasfasf' },
  { hash: 4047, val: 'kkkkkkkkkkkdddddddddkkkkkkkkkkddddddddd' },
  { hash: 4058, val: 'jfjfjfjfjfjfjfjfjfjfjfjfjfjfjfjfjfjfjfj' },
  { hash: 4081, val: 'ioudnjkanfjfhjhfjhakfshfkjhdajhkjafhkjf' },
  { hash: 4082, val: 'ioudnjkanfjfhjhfjhakfshfkjhdakhkjafhkjf' },
  { hash: 4082, val: 'oisdnkbgjkbajkgkbgkjbkklgjklsbkbfkjafas' },
  { hash: 4090, val: 'ioudnjsanfjfhjhfjhakfshfkjhdakhkjafhkjf' },
  { hash: 4099, val: 'asldfjlkcmclmasldkkjflksajflkjaljfljlfa' },
  { hash: 4101, val: 'sidfjlasjflijflijlfjliafjdlifjlijfiljfl' },
  { hash: 4105, val: 'iousnjsanfjfhjhfjhakfshfkjhdakhkjafhkjf' },
  { hash: 4125, val: 'iousnjsanfjfhlhfjuakfshkkjhdakhkjafhkjf' },
  { hash: 4128, val: 'sadnfjnfjnjfnjsdfnjafnjkfnkfnjkansdfjkn' },
  { hash: 4143, val: 'dnsfanfjknasfjklnaskfnkfnklafnjkfnkldsn' },
  { hash: 4150, val: 'dskfoisandginsgnlgn:nglngbtbiybuburubsu' },
  { hash: 4155, val: 'afadfsfsfsdfffsfsfsfsdfsfsfsdfsfsfsfsfs' },
  { hash: 4166, val: 'kjdkljkljkljlkjkljlkjlkjlkjlkjljlkjljlk' },
  { hash: 4211, val: 'jsanjnvjksnfkjsanfuiawngingiuilugniugng' },
  { hash: 4229, val: 'kllnlknlknklnklnlnlknknklnlnlnklnlknlkn' },
  { hash: 4238, val: 'lsniorhgpwoiqutoiuieofnionofnoinfonfioa' },
  { hash: 4349, val: 'iasfioehwoptqpoituopqwtuoquweporuqiorur' },
  { hash: 4374, val: 'ioequroiqwuroiuriouroiuopriuprouqpourrq' },
  { hash: 4377, val: 'iiuouoiuoiuouoiuuououoiuououoiuououoiuo' } ]

结果几乎是排序的，这意味着插入排序可以非常快地完成工作（请参阅 参考资料）。

如果这种粗略的实验提供了这些结果，那么肯定有一些解决方案在它的答案中丢失了。可能是哪个？

4

2 回答 2

3

下面的讨论是我冗长的说法，即您的想法（据我所知）在一般情况下不起作用。原因？因为两个长度为 N 的字符串之间的 Levenshtein 距离应该是 N，但是这些字符串具有相同的校验和。例如，反向字符串。此外，Levenshtein 距离为 1 的两个字符串之间的校验和差异可以是 255（或 Unicode 中的 65,536）。有了这样的范围，“几乎排序”，即使你能以某种方式做到这一点（见下文），也不会给你带来太多好处。

因此，您已经注意到简单校验和与 Levenshtein 距离之间的相关性。这是明显的关系。如果两个字符串之间的 Levenshtein 距离很小，那么这两个字符串包含大部分相同的字符。因此，简单校验和的计算将产生非常相似的值。有时。

然而，正如其他人指出的那样，相反的情况并非如此。字符串abcdef和fedcba具有相同的校验和，但是对于这么短的字符串，它们的 Levenshtein 距离相当大。

这不仅适用于逆转。例如，考虑字符串00000000。该字符串0000000~将具有比 大得多的校验和11111111，即使 Lev. 距离要小很多。

我想你会在一般情况下发现校验和和 Lev 之间的关系。距离是……有时是巧合。但是让我们忽略那个特定的问题，继续你关于排序的假设。

据我了解（老实说，您的问题在这一点上并不完全清楚），您想根据它们的 Levenshtein 距离对字符串列表进行排序。你没有说与什么的距离，但我假设在某个地方你有一个起始字符串，，S一堆其他字符串[S1, S2, S3, etc.]，并且你想按列夫对其他字符串的列表进行排序。距离S。

您的假设似乎是为每个字符串计算一个简单的校验和将使您能够更快地进行排序。

问题是，一旦计算了校验和，就必须对它们进行排序。传统的比较排序需要O(n log n)时间（无论如何，O(n)如果您有特殊用途的排序，至少需要时间）。一旦你得到了那个几乎有序的列表，你就必须计算 Lev。无论如何，然后重新排列列表顺序以反映实际距离。但有什么意义呢？

你必须计算列夫。无论如何，距离，你至少 O(n)会花时间整理一些东西。当您可以更快地计算 Lev 时，为什么还要费心计算和排序校验和。距离和排序？

于 2013-03-03T15:37:33.470 回答
1

O(n log n) 界限用于特定类型的排序，基于对有序类型的比较。

在这种情况下，您的排序基于一个简单的无符号整数值（取决于您正在处理的数据）可能是一个相当小的界限。在这种情况下，您的选择是...

  1. 如果最大距离足够小，则创建一个（最初为空）列表头指针数组。数组下标是距离。遍历您的数据以填充该列表数组，然后按顺序提取所有数据。如果您担心数组中的许多头指针保持为空（很多距离从未发生过），您还可以在数组中构建两个双链表 - 一个最初是未使用项目的完整列表，一个最初是空列表使用过的物品。这样，当您提取数据时，您只需查看其中包含项目的那些列表。

  2. 无论最大距离如何，您都可以使用哈希表做同样的事情。如果每次需要更多空间时表都以一个常数因子增长，则每次插入都需要 O(1) 时间amortized。当您考虑整个循环时，这变得简单 O(n) - 不再摊销 - 因为“摊销”的定义方式。哈希表通常是无序的，但你可以作弊 - 哈希是距离。可能需要更多的作弊来避免在提取数据时进行多次传递，但这不应该太难。

我认为尝试使用校验和没有任何好处。

如果要对数据进行排序，则无法击败 O(n)，因为您可能需要移动每个项目。即使您只是神奇地知道将每个项目移动到哪里，无论如何进行这些移动也是 O(n)。

此外，即使数据的顺序已经正确，只需计算距离即可确认也是 O(n)。

再想一想，我有点紧张，因为你不能只为一个字符串分配一个 Levenshtein 距离——它是相对于另一个字符串的。

如果您想建立字符串索引以便搜索“最近的”字符串，您可能应该查看Steve Hanov 博客上关于 Vantage Point Trees 的这篇文章。

不过，我怀疑你会得到 O(n) 的性能。

于 2013-03-03T15:59:33.353 回答