一千万个实体的恒定时间拼写校正
Constant-time Spelling Correction on Ten Million Entities
我有一个约 1000 万个实体的列表。我需要将用户键入的实体与列表中的实体进行匹配。用户经常拼错实体（即 orang 而不是 orange）。我需要更正 1-2 个字母替换实例（aca 代替 aba）、字母插入（aca 代替 ac）和字母删除（aca 代替 acca）。我想根据实体列表的大小在恒定时间内执行此操作。
制作一个包含所有可能相差 1-2 个字母的拼写的字典将是常数时间，但需要难以处理的大量内存。编辑距离相对于实体列表的大小在时间上是线性的。我在想可能有一个聪明的算法可以将候选匹配项 p运行e 降低到 <100（可能通过实体中字母的巧妙散列）。然后我可以 运行 编辑一小部分候选人的距离。
有人知道可以在这里使用的技术吗？
除了 Matt 评论中的链接文档（建议仅 generate/compare/search 通过删除），您可以尝试使用 DAWG aka MADFA aka DAFSA to store all possible distance=2 words. For example, for Python there's pyDAWG。不确定 space 节省是否足以满足您的需求，因为这取决于语言，但如果您的词缀相似，它可能非常重要：每个 substitution/deletion 只是一个额外的弧，并且每次插入只是多一个节点。
我有一个约 1000 万个实体的列表。我需要将用户键入的实体与列表中的实体进行匹配。用户经常拼错实体（即 orang 而不是 orange）。我需要更正 1-2 个字母替换实例（aca 代替 aba）、字母插入（aca 代替 ac）和字母删除（aca 代替 acca）。我想根据实体列表的大小在恒定时间内执行此操作。
制作一个包含所有可能相差 1-2 个字母的拼写的字典将是常数时间，但需要难以处理的大量内存。编辑距离相对于实体列表的大小在时间上是线性的。我在想可能有一个聪明的算法可以将候选匹配项 p运行e 降低到 <100（可能通过实体中字母的巧妙散列）。然后我可以 运行 编辑一小部分候选人的距离。
有人知道可以在这里使用的技术吗？
除了 Matt 评论中的链接文档（建议仅 generate/compare/search 通过删除），您可以尝试使用 DAWG aka MADFA aka DAFSA to store all possible distance=2 words. For example, for Python there's pyDAWG。不确定 space 节省是否足以满足您的需求，因为这取决于语言，但如果您的词缀相似，它可能非常重要：每个 substitution/deletion 只是一个额外的弧，并且每次插入只是多一个节点。