抽象算法：字符串/字節比較/比較

這是一個相當抽象的問題，因爲我還不知道如何解決它，並沒有找到任何合適的解決方案。抽象算法：字符串/字節比較/比較

讓我們從當前的情況開始。你會得到一組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

抽象算法：字符串/字節比較/比較

回答

相關問題