地圖字號碼

Question

我做數據的索引在我IRE（信息檢索和提取）過程。現在，不是將索引存儲在索引中，而是存儲termID，這是與該術語對應的映射。如果術語的長度是15，術語的大小將是15個字節，即120個比特，而如果我使用termID而不是術語，那麼我可以將它存儲在少於120個比特中。其中一種可能的方法是維護termID從1..n其中n是術語數量的（術語，術語ID）字典。這種方法的問題是：

1. 我必須在ram中保留這本字典，並且字典大小可以以GB爲單位。
2. 要找到對應於一個術語termID，它會採取爲O（log（n））的其中n是字典中的項數。

我可以做一些函數，它將一個詞作爲輸入並返回O（1）中的映射（加密）？如果有一些衝突是好的（只是猜測，在速度和內存交換一些碰撞是一個很好的權衡。順便說一句，我不知道會有多大影響我的搜索結果）。

是否有其他更好的方式來做到這一點？

Answer 1

我覺得你說「這是確定的，如果有一些衝突」已經或多或少給出了答案。訣竅是哈希。您可以先減少搜索條件中的「字符數」。例如，放置數字和特殊字符。之後，您可以合併大寫和小寫字符。最後，您可以應用一些簡單的替換，例如取代德國übei ue（這實際上是原產地）。這樣做後，你可能會有所作爲。像32位。然後，您可以在一個字節中表示四個字符的字符串。如果您爲每個單詞保留4個字節，則需要處理較長的單詞。在那裏你可以基本使用xor每個4字節塊。

另一種方法是對字典做一些混合。如果你只爲最常用的10k字建立一本字典，你很可能已經覆蓋了大部分的文本。因此，您只需要將字典的部分內容保存在內存中，而對於大多數單詞，您可以在hardisc上使用字典，或者甚至可以忽略它們。