我想使用Locality敏感哈希来大致匹配字符串.我有很多字符串> 10M可能包含错别字.对于每个String,我想与所有其他字符串进行比较,并根据某个阈值选择具有编辑距离的字符串.
也就是说,天真的解决方案需要O(n ^ 2)个比较.为了避免这个问题,我正在考虑使用Locality Sensitive Hashing.然后接近相似的字符串会产生相同的桶,我只需要在桶搜索中进行.所以它是O(n*C),其中C是桶大小.
但是,我不明白如何表示字符串.如果是文本,我将在向量空间中表示.我的主要问题是,如果使用LSH这是易处理的,然后是字符串的适当矢量表示.
我可以使用已经实现的库来执行此任务吗？或者这取决于我的问题,所以我必须自己实施？是否有任何python包执行此操作？
我想比较两个字符串,以便比较应忽略特殊字符的差异.那是,
海,这是一个考验
应该配合
海!这是一个测试"或"海这是一个测试
有没有办法在不修改原始字符串的情况下执行此操作？