查找十六進制文件中的模式

Question

我有兩個不同的文件，每個文件的內容來自不同的數據流。我從兩個不同的文件中收集了來自這些流的一些數據。然後，我想搜索文件以查找任何類型的模式，以便在稍後階段如果我從流中收集更多數據，我應該能夠區分哪些數據屬於哪個流（基於我發現的模式更早）。

該文件中包含的數據的一個示例可以是：b0 82 91 a2 c3 89 b0 82 4a e3 ....（更多字節）... 雖然我在這裏佔用了很少的字節，但我們可以找到上面兩次出現的模式「b0 82」。所以輸出結果應該顯示模式和它未來的時間。類似的，我們可以有3字節模式或甚至更多的字節模式。

其他示例可以是：aa 00 a7 2f 7b 4c ....（更多字節）..... aa 01 a7 .........（更多字節）..... .aa 05 A7 ..... 我認爲，即使這可以被認爲是3個字節，其中兩個字節（AA & A7）是固定的，中間的一個從00到05。

變化的圖案這些兩個例子我可以想到，雖然可能會有更多的圖案。即使可能有一些隱藏的模式不能立即可視化。只要有助於在稍後階段區分兩股流股，整個想法是可行的。我想我現在更清楚地說明我的問題。請讓我知道以下幾件事：

1. 我們該如何做這種類型的模式查找？

2. 是否有任何工具或庫可以幫助實現此目的？

3. 還有哪種語言或工具可用於高效快速的開發？

4. 數據挖掘領域可以爲此目的提供幫助嗎？如果是的話，如何繼續？

Answer 1

你的問題沒有完全確定，但我會盡量給你幾個指針：

1. 你的模式很可能表達爲正則表達式。如果你不知道這些是什麼 - 我會試着用你最喜歡的編程語言尋找一個具體的例子。 Python是一個很好的選擇（re模塊包含在覈心語言中）。對於C++，使用boost :: regex和其他語言，請使用google :)

2. 現在 - 使用正則表達式來搜索二進制文件（十六進制）而不是文本，請嘗試查看諸如this之類的內容。

祝你好運:)

Answer 2

這是另一種思路。它是否適用於您取決於您​​正在處理的數據量，可以使用多少內存，以及它檢測到的模式種類是否最終可用於您的目的。

考慮到所有這些資格，則可能需要使用後綴樹或後綴數組嘗試。特別是對於後綴樹，有一些算法使您能夠在將字符附加到文本（所謂的在線後綴樹構造）（最值得注意的是Ukkonen算法）時不斷更新樹。這可能對數據流的使用特別有效（與固定長度，完全定義的輸入文本相反）。

後綴樹（以及類似的方式，後綴數組）表示文本的所有後綴（在字符串結尾，而不是語言後綴）。因此，它特別適用於（a）檢查任何給定的字符串是否爲文本的子字符串，以及（b）用於檢測文本中的子字符串。通過在正確位置進行一些修改，它可以用來檢測重複的子字符串，並稍做修改（就像您在中間交換一個字符時重複的模式示例）。

要全面瞭解這些數據結構，並且如果您有權訪問大學圖書館或有錢，Dan Gusfield's introduction to algorithms on strings, trees and sequences將非常有幫助。但是也有一些與此相關的問題和答案。

如果在進一步閱讀之後，您認爲值得一試，我可以進一步詳細闡述我如何認爲後綴樹可以用於您的目的，以及針對使用這些算法的新問題的答案重複模式檢測。

Answer 3

您可以在您的流上訓練Markov Models甚至隱藏馬爾可夫模型，並使用這些模型來確定最可能屬於哪個新數據流。據說有幾十個庫可以在你選擇的編程語言中做到這一點。

也許從讀一本書開始。我建議C. Bishop的Pattern Recognition。

Answer 4

這似乎是一個非常典型的ngram發現問題。這裏是一些ngram解決方案的鏈接。

quicker way to detect n-grams in a string?

你應該把你的十六進制就像任何其他字符串。