字符串的哈希函数

Question

我正在寻找一种哈希函数表，用于存储长度较短的字符串集合（每个字符串的长度小于50），具有特殊功能：每当我们在此表中搜索一个字符串时，如果该字符串在表中，则返回与该字符串相关联的对象或特定唯一数字；如果该字符串不在表中，则返回与输入相似度非常高的字符串的ID。 为了定义两个字符串之间的相似度，我们可以定义不同的函数，但假设我们将其定义为将一个字符串转换为另一个字符串所需的最小操作数。 三点说明：

1. 查询字符串和保存字符串的长度始终相似且固定。
2. 字符串的字母表仅限于5个不同的字符。
3. 当然，对我来说，内存和速度都很重要。

我不是在寻找最终解决方案，但欢迎任何建议或介绍类似情况下采用类似方法的论文。

- user2373198

---

@KarolyHorvath：我怀疑字符串的长度小于50，而不是字符串的数量。 - Igor Tandetnik

选择一个通用的哈希函数来处理字符串，并对数组中的元素进行排序。搜索可以简化为二分查找。 - Raxvan

你能向表格中添加新元素吗？ - Karoly Horvath

关于相似性，短的子字符串（例如二元组）是否特别有意义？ - greybeard

你正在寻找一种局部敏感哈希算法；Google可以帮到你。LSH用于近似最近邻搜索，这与你所需的类似。 - Stefan Atev

Answer 1

如果字符串集是有限的且已知的，则考虑使用 GPERF 生成完美哈希函数。

接着对 SOUNDEX(string) 进行哈希，使用链接列表来解决冲突。

使用第一组进行精确查找。使用第二组进行近似匹配。

编辑：由于你的字母表只有5个字符，你可以创建多个哈希表以减少 N 的大小。

预处理键，识别每个唯一的字母。它可能是一个只有 A 的键 AAAAA。也可能是 AB 或 ABCDEF 的键 AABBBB。有大约 5！这些。120 根进入哈希树，如有需要可使用单独的哈希函数。

我有些担心，因为不清楚字符串实际存储在哪里。很有可能哈希会出现冲突。你打算如何解决？将哈希散列到寻址列表中，这样可以通过从磁盘读取实际字符串来验证正确的哈希吗？

- EvilTeach

---

已知一组字符，但对于固定长度，存在任何这些字符的组合的可能性。 - user2373198