我有一个大型数据库（可能有数以百万计的记录），带有较短的文本字符串（按街道地址，名称等的顺序）。

我正在寻找一种删除不精确重复项的策略，而模糊匹配似乎是选择的方法。我的问题：许多文章和SO问题都涉及将单个字符串与数据库中的所有记录进行匹配。我希望立即对整个数据库进行重复数据删除。

前者是一个线性时间问题（将一个值与一百万个其他值进行比较，每次都计算一些相似性度量）。后者是一个指数时间问题（将每条记录的值与其他每条记录的值进行比较；对于一百万条记录，大约是5
x 10 ^ 11的计算，而前一种选择是1,000,000的计算）。

我想知道是否有除我提到的“强力”方法以外的其他方法。我正在考虑可能要生成一个字符串来比较每个记录的值，然后将具有相似相等度量的字符串分组，然后在这些组中运行蛮力方法。我不会达到线性时间，但这可能会有所帮助。另外，如果我正在考虑正确的话，这可能会错过字符串A和B之间潜在的模糊匹配，因为尽管它们彼此非常相似，但它们与字符串C（生成的检查字符串）的相似性却非常不同。

有任何想法吗？

PS：我意识到我可能使用了错误的术语来表示时间复杂度，这是我基本掌握的概念，但还不够好，因此我可以将算法归类为适当的类别。
如果我使用错误的术语，我欢迎进行更正，但希望至少我能理解我的意思。

编辑

考虑到记录之间的模糊匹配，一些评论者问我应该采取什么策略来选择要删除的记录（即给定的“ foo”，“ boo”和“
coo”，这将被标记为重复并删除）。我应该注意，我不是要在此处自动删除。这个想法是在60亿以上的记录数据库中标记潜在的重复项，以供人工检查和评估之用。只要有一个大致可预测的/一致的数量，就可以有一些误报。我只需要了解重复项的普及程度。但是，如果模糊匹配传递需要一个月的时间才能运行，那么这甚至根本不是一个选择。