fuzzy-search

fuzzy-search 提供了模糊搜索的集合，允许您高效地找到与模式大致匹配的字符串。它利用BK树、Levenshtein自动机和SymSpell等算法，实现快速准确的模糊搜索。

动机

BK树、Levenshtein自动机和SymSpell算法背后的动机在于它们能够优化模糊搜索过程，特别是当你想要在choices中找到编辑距离为N或更小的字符串时。它们通过减少实际编辑距离计算的必要性来实现这种优化。这些算法通过采用称为“剪枝”的技术来提高搜索过程的效率，该技术可以移除那些肯定在所需编辑距离之外的选项，从而显著减少计算开销。

例如，考虑以下代码，它直接计算Levenshtein距离并返回最大编辑距离（max_edits）内的字符串

pub fn fuzzy_search<E>(
    query: &str,
    choices: &[String],
    max_edits: usize,
) -> Vec<String>
where
    E: Fn(&str, &str) -> usize + Sync,
{
    choices
        .iter()
        .filter(|choice| levenshtein(query, choice) <= max_edits)
        .cloned()
        .collect()
}

虽然这种方法有效，但它可能计算成本很高，尤其是对于大型数据集。BK树、Levenshtein自动机和SymSpell通过采用各种剪枝策略来解决这个问题，这些策略在搜索过程中早期就排除了候选字符串。这种优化显著减少了编辑距离计算的数量，使得模糊搜索更加高效，特别是在编辑距离相对较大或数据集广泛的情况下。

特性

• BK-Tree
• Levenshtein自动机
  • 有关实际实现的详细信息，请参阅这篇文章。
• SymSpell

安装

将以下行添加到您的Cargo.toml文件中，以将此库包含到项目中

[dependencies]
fuzzy-search = "0.1"

示例

BK-Tree

extern crate fuzzy_search;

use fuzzy_search::bk::BkTree;

fn main() {
    let choices = // put strings for fuzzy search

    let mut bk = BkTree::new(levenshtein, 2);
    for c in choices {
        bk.insert(c);
    }
    println!("{:?}", bk.fuzzy_search("food").len());
}

Levenshtein自动机

extern crate fuzzy_search;

use fuzzy_search::automata::LevenshteinAutomata;

fn main() {
    let choices = // put strings for fuzzy search

    let automata = LevenshteinAutomata::new("food", 2);
    println!("{:?}", automata.fuzzy_search(&choices).len());
}

SymSpell

extern crate fuzzy_search;

use fuzzy_search::symspell::SymSpell;

fn main() {
    let choices = // put strings for fuzzy search

    let mut sym = SymSpell::new(levenshtein, 2);
    for c in choices {
        sym.insert(c);
    }
    println!("{:?}", sym.fuzzy_search("food").len());
}

许可证

本项目采用MIT许可证。有关详细信息，请参阅LICENSE文件。