抽象算法：字符串/字节比较/比较

这是一个相当抽象的问题，因为我还不知道如何解决它，并没有找到任何合适的解决方案。抽象算法：字符串/字节比较/比较

让我们从当前的情况开始。你会得到一组byte[]（例如ArrayList<byte[]>），幕后实际上是字符串，但在当前状态byte[]是首选。它们可能非常长（每个byte[]阵列的1024+字节，而ArrayList可能包含多达1024个byte[]阵列），并且可能具有不同的长度。此外，它们在“相同”位置共享很多相同的字节（这是相对的，a = {0x41，0x41，0x61}，b = {0x41，0x41，0x42，0x61} =>其中第一个0x41和最后的0x61是相同的）。

我正在寻找一种算法，将所有这些数组相互比较。结果应该是最不相同的数组以及它们相互之间的差异程度（某种度量标准）。此外，该任务应在短时间内完成。

如果可能，不使用任何第三方库（但我怀疑这是可行的在没有一个合理的时间）。

任何建议都非常欢迎。

编辑：

做了一些调整。

编辑/解决方案：

我使用的是莱文斯坦距离现在。此外，我做了一些微调，以提高运行时间/速度。这对我处理的数据非常具体，因为我知道所有的字符串都有很多共同点（我大概知道它在哪里）。因此，与Levenshtein距离算法直接使用的两个未过滤字符串（测试数据）相比，过滤该内容可将速度提高400倍。

感谢您的输入/答复，他们是一个很好的帮助。

来源

2016-04-14 Code Monkey

不清楚。 “你将有一个byte []”=> 1数组的数组。 “它们可以很长（每个〜1024个字节）”=>至少2个数组。那里有多少？无论如何，答案可能都是对所有Levenshtein距离;去谷歌上查询。 –

@j_random_hacker - 谢谢你的回答。我已经在研究Levenshtein距离，但是读到它对长字符串表现不佳（这可能是这种情况？没有找到确切长度的定义）。此外，你比较2个字符串，而不是一堆字符串，这让我想知道你需要比较哪些字符串（你没有“基线”）。关于“不清晰”的部分：我调整了这个问题，它是一个ArrayList 而ArrayList的大小高达1024，每个byte []数组的大小是1024 - 未定义（非常长...> _ < ） –

由于您必须处理1024和* undefined *之间的某个大小，因此Array是一个非常糟糕的选择。如果可能的话，你应该使用一些可以无限增长的结构，例如您选择的“List”实施。即使Levenshtein距离如果计算起来昂贵，它似乎也是这里的相关度量。将所有数组与所有数组进行比较，也将具有O（n2）的运行时特性，其可靠性不会很快*。 – nitowa

我现在正在使用Levenshtein距离。此外，我做了一些微调，以提高运行时间/速度。这对我处理的数据非常具体，因为我知道所有的字符串都有很多共同点（我大概知道它在哪里）。因此，与Levenshtein距离算法直接使用的两个未过滤字符串（测试数据）相比，过滤该内容可将速度提高400倍。

感谢您的输入/答复，他们是一个很好的帮助。

来源

2016-04-25 13:15:00

结果应该是最不相同的数组以及它们相互之间的差异程度（某种度量标准）。此外，该任务应在短时间内完成。

您将无法找到解决方案，其中您的指标和时间是独立的，它们并行不悖。

例如：如果您的指标与您帖子中的示例相似，即d(str1,str2) = d(str1.first,str2.first) + d(str1.last,str2.last)，那么解决方案非常简单：按照第一个和最后一个字符（可能单独）对数组进行排序，然后取第一个和最后一个元素排序后的数组。这会给你O(n logn)的排序。

但是，如果您的度量标准类似于“如果两个句子包含许多相同的单词都很接近”，那么这根本就不起作用，最终以O(n²)结束。或者你可以想出一个巧妙的方法来重新排列句子中你的话整理句子等等，等等

所以，除非你有一个已知的指标，它是O(n²)与琐碎之前（幼稚）实现比较所有内容，同时跟踪最大增量。

来源

2016-04-14 16:21:40 AnoE

抽象算法：字符串/字节比较/比较

回答

相关问题