在壓縮文本文件中快速搜索

Question

我需要能夠搜索大量壓縮文件（.txt）中的文本。壓縮可能會改變成其他東西，甚至變成專有的。 我想避免解壓縮所有文件，並壓縮（編碼）搜索字符串並在壓縮文件中搜索。對於所有文件，這應該可以使用具有相同碼本的霍夫曼壓縮。 我不想重新發明輪子，所以..任何人都知道一個類似這樣的庫或者執行並測試了霍夫曼算法的庫，或者更好的主意？

在此先感謝

Answer 1

大多數文本文件都使用LZ-family算法進行壓縮，該算法將Dictionary Coder和Entropy Coder（如Huffman）組合在一起。

由於字典編碼器依賴於不斷更新的「字典」，其編碼結果取決於歷史（從輸入數據到當前符號的字典中的所有代碼），所以它不是可能跳到某個位置並開始解碼，而不先解碼所有先前的數據。

在我看來，你可以使用一個zlib流解碼器，它可以在解壓縮完整文件的時候返回解壓縮的數據。這不會節省執行時間，但會節省內存。

第二個建議是對英文單詞進行霍夫曼編碼，並忘記字典編碼器部分。每個英文單詞被映射到一個獨特的無前綴代碼。

最後，@SHODAN給出了最明智的建議，即索引文件，壓縮索引並捆綁壓縮文本文件。要進行搜索，只需解壓縮索引文件並查找單詞。這實際上是對單詞進行霍夫曼編碼的改進 - 一旦您找到單詞的頻率（爲了優化分配前綴代碼），您已經構建了索引，因此您可以保留索引以進行搜索。

Answer 2

我可能是完全錯誤的在這裏，但我不認爲會是搜索一個給定的字符串沒有文件解碼的可靠方法。我對壓縮算法的理解是，對應於給定字符串的比特流將非常依賴於未壓縮文件中的字符串之前的內容。您可能能夠找到給定文件中特定字符串的給定編碼，但我很確定它們在文件之間不一致。

Answer 3

您不可能在壓縮文件中搜索未壓縮的字符串。我想你最好的選擇之一是以某種方式索引文件。也許使用Lucene？

Answer 4

在壓縮文件中搜索文本可能比在未壓縮文本文件中搜索同樣的東西快。我見過

一種壓縮技術，即犧牲，以一定的空間，做到快速搜索：

• 保持與文本的每一個字的2^16個條目的字典。爲字面字節保留前256個條目，以防萬一找到不在字典中的單詞 - 即使許多大文本的唯一字數少於32,000，因此它們永遠不需要使用這些字面字節。
• 通過將16位字典索引替換爲每個字來壓縮原始文本。
• （可選）在正常情況下，兩個單詞由一個空格字符分隔，放棄該空格字符;否則將字符串之間的字符串中的所有字節放入字典中作爲用「無默認空格」屬性標記的特殊「字」（例如，「。」和「，」和「\ n」），然後「compress 「這些字符串通過替換它們與相應的字典索引。
• 通過以相同的方式壓縮該短語來搜索單詞或短語，並且以與在原始文本中搜索原始字符串的方式完全相同的方式在壓縮文本中搜索壓縮的字節串。

特別地，搜索一個字通常會減少到比較在壓縮的文本，這是比搜索原始文本字更快的16位索引，因爲

• 每個比較需要比較較少的字節數 - 2，而不是那個字中包含的字節數，並且
• 由於壓縮文件更短，因此我們正在進行較少的比較。

有些種類的正則表達式可以轉換到另一個正則表達式的直接查找壓縮文件中的項目（也或許也發現一些假陽性）。 這樣的搜索也比在原始文本文件上使用原始正則表達式做的比較少，因爲壓縮文件較短，但通常每個正則表達式比較需要更多的工作，所以它可能會或可能不會比原始正則表達式運行更快在原文上。

（原則上你可以用長度可變的霍夫曼前綴代碼替換固定長度的16位代碼，正如rwong所提到的那樣 - 得到的壓縮文件會更小，但處理這些文件的軟件將是慢一點，也很複雜）。

對於更復雜的技術，你可能看

• MG4J：Managing Gigabytes for Java
• "Managing Gigabytes: Compressing and Indexing Documents and Images"由伊恩·H·威滕，阿利斯泰爾·莫法特，和Timothy C.貝爾

Answer 5

這是可能的，並且可以非常有效地完成。關於這個主題有很多令人興奮的研究，更正式地稱爲簡潔數據結構。我建議研究一些主題：小波樹，FM索引/ RRR，簡潔後綴數組。正如許多出版物所證明的，您也可以高效地搜索Huffman編碼的字符串。