在过去的一个月里,我一直在花大量时间替换我的写作和编程环境中的一个关键组件:我的语法检查器。
到目前为止,我一直通过 ltex-ls[1] 和 nvim-lspconfig[2] 使用同名的 LanguageTool[3] 。不要误会,这些工具真的很好,我会推荐给任何人。然而,它们也有一些关键的烦恼。
LanguageTool的不足
性能
LanguageTool很慢。我不太确定为什么。每次我在我的Markdown或LaTeX\LaTeX文档(大小适中)上运行LanguageTool时,我都要等待几秒钟,甚至最基本的拼写检查才会出现。
此外,我发现ltex-ls经常成为我笔记本电脑上最耗内存的应用程序,通常超过4GB。
经过数小时搜索他们的代码库,我得出的唯一解释是它是用Java编写的。里面还有一些值得质疑的算法决策。
下载大小
正如我所说:LanguageTool确实非常好。然而,要获得它所能提供的一切,你不仅需要安装Java运行时环境(在我的系统上>150 MB),实际的.jar文件(>300 MB),还需要下载16 GB的n-gram数据集。
Grammarly的不足
"但是Elijah,"我听到你说,"直接用Grammarly吧!"
**不。**我不会为一个更慢更差的东西每月花12美元。更不用说他们可能会用我的作品来训练他们的大型语言模型。Grammarly是一个很棒的产品,只是不适合我。
算法
现在我已经彻底解释了我实现新语法检查器的原因(我称之为 Harper[4] ),我想回顾一下我第一次尝试拼写检查的过程,诚然这是一个天真的尝试。
我们需要掌握的第一个概念是_Levenshtein编辑距离_。本质上,编辑距离是将一个单词转换为另一个单词所需的最少单字符编辑(插入、删除或替换)次数。例如,"cat"和"bat"之间的编辑距离是1;唯一的编辑涉及将"c"替换为"b"。
同样,"kitten"和"sitting"之间的编辑距离是3:删除"g",将第二个"i"替换为"e",并将"s"替换为"k"。对于这种天真的拼写检查,我们不太关心给定拼写错误中发生的确切编辑(原子错误),只关心错误的大小。
从高层次来看,算法将如下工作:
- 确定给定单词是否拼写错误。如果没有,退出。
- 计算拼写错误的单词与所有有效英语单词之间的Levenshtein编辑距离。
- 选择编辑距离最短的三个单词,并将它们呈现给用户作为替代拼写选项。
步骤1
要确定给定单词是否拼写错误,我们需要一个包含英语中所有有效单词的列表。事实证明,这并不容易。今天,我们将只使用英语的一个子集,使用这个简短的列表:
into the a cat tree jumped
要检查给定单词是否在列表中,我们可以将列表放入哈希集中,并获取其内容。
let words: Vec<String> = vec!["into", "the", "a", "cat", "tree", "jumped"] .into_iter() .map(|s| s.to_string()) .collect(); let word_set: HashSet<String> = words.iter().cloned().collect(); let word = "thw"; let word_chars: Vec<_> = word.chars().collect(); if word_set.contains(word) { println!("It is a valid English word!"); return; } println!("Are you sure you meant to spell \"{}\" that way?", word);
Wagner-Fischer算法
现在我们知道我们的单词实际上拼写错误了,我们可以继续寻找正确的拼写。我们需要找到拼写错误的单词与我们集合中所有单词之间的编辑距离。
为此,我们将使用 Wagner-Fischer[5] 算法。
// Computes the Levenstein edit distance between two patterns. // This is accomplished via the Wagner-Fischer algorithm fn edit_distance(source: &[char], target: &[char]) -> u8 { let m = source.len(); let n = target.len(); // Create an m-by-n matrix. let mut d = create_empty_matrix(m + 1, n + 1); // Since we know we can transform each word into the other by replacing // successive characters (or deleting them), we can fill the first column and // row with values from 0..m and 0..n, respectively. for i in 0..=m { d[i][0] = i as u8; } for i in 0..=n { d[0][i] = i as u8; } for j in 1..=n { for i in 1..=m { // The total edit distance of two given letter indices i and j, one from each word // will be the sum of the edit distances of prior combinations + whether the characters // at the two indices are equal. let cost = if source[i - 1] == target[j - 1] { 0 } else { 1 }; d[i][j] = (d[i - 1][j] + 1) .min(d[i][j - 1] + 1) .min(d[i - 1][j - 1] + cost); } } // After all possible edits have been explored and minimized // the resulting minimum edit distance will be in the final item in the matrix. d[m][n] } // Create an empty matrix of size [m, n] fn create_empty_matrix(m: usize, n: usize) -> Vec<Vec<u8>> { let mut d = Vec::with_capacity(m); for _ in 0..m { d.push(vec![0u8; n]); } d }
这工作得很好。我们可以对这个函数单独应用一些优化。我将把这个问题留给读者,因为它们与更大算法的核心并不特别相关。
步骤2 + 3
现在我们可以确定两个单词之间的编辑距离,我们可以执行暴力搜索。在这个简短的例子中,我们将使用sort_by_key来做这个,因为我们的数据集非常小。如果我们使用更大的字典(比如说,整个英语语言),我们需要做一些事情来减少时间和内存消耗。
let mut suggestions: Vec<(String, u8)> = words .into_iter() .filter_map(|possible_word| { let possible_chars: Vec<_> = possible_word.chars().collect(); let dist = edit_distance(word_chars.as_slice(), &possible_chars); if dist <= 2 { Some((possible_word, dist)) } else { None } }) .collect(); suggestions.sort_by_key(|(_, d)| *d); println!("Possible alternatives: "); suggestions.iter().for_each(|(s, _)| println!("- {}", s));
如果我们再次运行整个程序,我们会得到类似这样的输出:
Are you sure you meant to spell "thw" that way? Possible alternatives: - the
我觉得这看起来不错!
如果你想查看整个程序,也许尝试你自己的输入, 请随意[6] 。
参考链接
ltex-ls: https://github.com/valentjn/ltex-lsnvim-lspconfig: https://github.com/neovim/nvim-lspconfig- LanguageTool: https://languagetool.org/
- Harper: https://github.com/elijah-potter/harper
- Wagner-Fischer: https://en.wikipedia.org/wiki/Wagner–Fischer_algorithm
- 请随意: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=fb7910ad1fb3a6c944cbc2ae8659bb31
