在大的二進制文件中搜索字符串

Question

我有一個大的二進制文件（1 MB <大小< 50 MB）。我需要搜索一個字符串並提取後續的四個字節（這是另一個文件中實際數據的{大小，偏移量}）。什麼是最有效的方法，以便搜索速度最快？

編輯：索引文件中的字符串按排序順序。

Answer 1

按排序順序（按字符串）存儲{字符串，大小，偏移量}元組，並使用二進制搜索字符串。

您也可以在文件開始時爲字符串的每個首字母存儲偏移量。例如，如果以'a'開頭的字符串從位置120開始，那些以'b'開頭的文件從文件的位置2000開始，則可以使用如120, 2000, ...

Answer 2

如果編碼是固定的（ASCII），則相對簡單。打開一個二進制流，爲字節讀取字節並與目標字符串的第一個字符匹配。

如果你有使用另一個（UTF-8）編碼的字符串，它會變得更加棘手。

Answer 3

查找Boyer–Moore string search algorithm。

Answer 4

首先，在文件上使用內存映射。這比將其讀入RAM更高效，因爲不是兩個副本（一個在你的程序中，一個在文件高速緩存中）只有一個副本。

如果每個字符串都是固定長度，那麼二分法搜索非常容易，因爲您可以將內存視爲字符數組的數組。

如果每個字符串終止變長，但0，那麼你可以使用二進制搜索的一個變種，你跳轉到字符串列表的中間，尋找下一個0，然後測試之後，下一個字符串。然後向前或向後跳轉到字符串列表的1/4或3/4並重復。

如果每個字符串都是Pascal風格的可變長度，並且字節數在開始時更加棘手。從一開始的線性搜索不會太慢，對於不頻繁的搜索。如果你正在尋找確切的字符串匹配，不要忘記，你可以通過檢查長度不匹配來跳過大多數字符串。

如果你要搜索列表中經常要建設字符指針數組的字符串列表將再次使二進制搜索很容易。如果該文件是真的快速搜索的索引文件，那麼它可能已經在某個地方有這個，除非設計者意在建立一個字符指針數組，而加載文件。