Node.js中的分布式高速咒语检查和校正-DEV365 开发者社区

介绍

拼写检查是软件应用程序中广泛使用的功能，例如搜索引擎，电子邮件客户端，文字处理器和聊天机器人。

SymSpellEx（扩展的Symspell）

node.js拼写校正和模糊搜索库，基于对称删除拼写校正算法（Symspell）

为什么symsspellex

简单的拼写检查算法，例如Norvig算法，不有效且可能很慢。
我需要一个拼写检查器，该检查器可以在带有多个节点的分布式系统上使用，以执行拼写校正，而无需复制每个节点上的数据。
我需要确保对培训数据的任何更改或更新将反映在所有连接的节点中。

编辑距离

编辑距离是根据将一个字符串转换为另一个字符串所需的最小操作数量的两个字符串的度量。

编辑距离算法计算将一个字符串转换为另一个字符串所需的最小编辑操作数量，其中编辑操作包括插入，删除和替换字符。一些流行的编辑距离算法包括：

Levenshtein距离：此算法计算将一个字符串转换为另一个字符串所需的插入，删除和替换的最小数量。
Damerau-Levenshtein距离：这类似于Levenshtein距离，但也允许进行换位（即交换相邻字符）。
jaro距离：此算法根据匹配字符的数量和使字符串相同所需的换位数来计算两个字符串之间的相似性。
jaro-winkler距离：这是jaro距离的扩展，将更高的权重分配给前缀匹配。

例子

“小猫”和“坐着”之间的levenshtein距离是3。将前者转换为后者的最小编辑脚本是：

kitten → sitten (substitute "s" for "k")
sitten → sittin (substitute "i" for "e")
sittin → sitting (insert "g" at the end)

将“小猫”变成“坐着”所需的操作总数是三个，这是两个字符串之间的编辑距离。

天真的方法

它涉及检查字典中的每个单词以找到与拼写错误的单词最小的编辑距离的单词。

例如，如果拼写错误的单词是“ teh”，则该算法将检查字典中的每个单词，以找到具有最小编辑距离的单词。该算法可能会发现“ The”是一种可能的校正，因为它仅需要一个编辑（用“ E”替换为“ H”）

这种方法在计算上非常昂贵，因此使用不切实际。

彼得·诺维格算法

彼得·诺维格（Peter Norvig）算法是一种拼写检查算法，它以与查询术语的给定编辑距离生成所有可能的术语，并在字典中搜索它们以找到正确的拼写。编辑距离是根据将查询术语转换为正确拼写所需的操作数量计算的，其中操作可以是单个字符的删除，换位，替换或插入。

该算法遵循以下步骤：

通过将删除，换位，替换和插入应用到输入单词。
过滤候选词，以仅保留出现在先前存在的文本中的单词，在这种情况下，是一个大的英语文本语料库。
根据其在语料库中发生的频率对剩余的候选单词进行排名。
返回最有可能的候选单词作为校正的拼写。

示例：
假设输入词是“ the”，我们有一个大的英语文本语料库可从中汲取灵感。我们首先在“ The”的2个编辑距离内生成所有可能的候选单词。这给我们提供了一组诸如“ thee”，“他们”，“”，“”，“这些”，“ theta”等词。

接下来，我们将此集合过滤为仅包括出现在英语文本语料库中的候选单词。假设这将我们的套装缩小到“和“他们”。

最后，我们通过在语料库中发生的频率对剩余的候选单词进行排名。由于“ the”是英语中非常普遍的词，因此比“他们”更有可能是预期的拼写。因此，“返回”作为输入词的校正拼写“。”。

但是，这种方法可能是昂贵且依赖语言的。对于长度为n的单词，字母大小A和1个编辑距离为1，将有n删除，n-1 transostoss，a * n更改和a * (n+1)插入。

候选单词编号可以使用：
计算 2n+2an+a-1或54n + 25（假设我们使用的是具有a = 26的英语字母），将导致90902候选单词搜索。

在某些语言中，例如中文，字母可能是巨大的，从而导致更多的单词可以搜索。

对称删除拼写校正算法

对称删除拼写校正算法简化了在字典中生成可能的拼写和搜索的过程。它仅将删除作为操作而不是与转置，替换和插入操作相结合的删除来做到这一点。结果，它的速度要快得多，比传统的编辑距离的六个数量级要快。此外，它是独立的。

为什么该算法快速？

在训练阶段进行预计算，而所有可能的拼写误差变体（仅删除）并存储在哈希表中，这在搜索搜索时间的平均搜索时间复杂性（1）时也很快。

这使该算法非常快，但也需要大量的内存足迹，训练阶段需要大量时间才能第一次构建字典。

有关更多详细信息检查SymSpell

symspellex

Symspellex正在Symspell上构建，以通过实现不同的编辑距离算法或实现不同的数据存储来提供可扩展性。

特征

非常快
单词建议
单词校正
支持多种语言 - 算法，实现是语言独立的
可扩展 - 可以实现编辑距离，并且可以实现数据存储以扩展库功能

主要成分

1.令牌

可以实现此接口以为库提供不同的令牌，提供了一个简单的核心令牌。

export interface Tokenizer {
    tokenize(input: string): Array<Token>;
}

2.编辑距离

可以实现此界面以提供不同的算法来计算两个单词之间的编辑距离。

interface EditDistance {
    name: String;
    calculateDistance(source: string, target: string): number;
}

内置编辑距离算法

Damerauâlevenshtein距离

3.数据存储

可以实现此界面以提供其他方法来存储内置商店（内存，redis）

以外的数据

数据存储应处理这两种数据类型的存储：

术语：列出数据结构以存储术语并通过索引检索
条目：哈希表数据结构以存储字典条目并按学期（键）检索数据

数据存储还应处理多种语言的存储，并在它们之间切换，检查实现的数据存储。

export interface DataStore {
    name: string;
    initialize(): Promise<void>;
    isInitialized(): boolean;
    setLanguage(language: string): Promise<void>;
    pushTerm(value: string): Promise<number>;
    getTermAt(index: number): Promise<string>;
    getTermsAt(indexes: Array<number>): Promise<Array<string>>;
    getEntry(key: string): Promise<Array<number>>;
    getEntries(keys: Array<string>): Promise<Array<Array<number>>>;
    setEntry(key: string, value: Array<number>): Promise<boolean>;
    hasEntry(key: string): Promise<boolean>;
    maxEntryLength(): Promise<number>;
    clear(): Promise<void>;
}

内置数据存储

内存：将数据存储在内存中，使用术语和高速哈希表（Megahash）管理字典条目

可能会受到节点过程内存限制的限制，可以覆盖

redis：使用列表结构将数据存储到REDIS数据库中，以存储术语和哈希存储字典数据

非常有效地培训和存储数据的方法，它将允许通过多个过程和/或节点/机器访问，一次在集中式分布式商店上培训数据，并且可以使用REDIS上的不同命名空间在生产中更新足够的内存数据中断，倾倒和迁移数据将很容易。

redis数据存储使用LUA脚本来通过定义自定义命令hSetEntry
在服务器端上使用多个redis命令有效设置条目

async initialize(): Promise<void> {
        await this._redis.defineCommand('hSetEntry', {
            numberOfKeys: 2,
            lua:
                `
                local olen = redis.call("hget", "${this._configNamespace}", ARGV[2])
                local value = redis.call("hset", KEYS[1], KEYS[2], ARGV[1])
                local nlen = #KEYS[2]
                if(not olen or nlen > tonumber(olen)) then
                  redis.call("hset", "${this._configNamespace}", ARGV[2], nlen)
                end
                return value
                `
        });
        this._initialized = true;
    }

用法

训练

对于单学期培训，您可以使用add函数：

import {SymSpellEx, MemoryStore} from 'symspell-ex';

const LANGUAGE = 'en';
// Create SymSpellEx instnce and inject store new store instance
symSpellEx = new SymSpellEx(new MemoryStore());
await symSpellEx.initialize();
// Train data
await symSpellEx.add("argument", LANGUAGE);
await symSpellEx.add("computer", LANGUAGE);

对于多个术语（数组）您可以使用train函数：

const terms = ['argument', 'computer'];
await symSpellEx.train(terms, 1, LANGUAGE);

搜索

search功能可用于获取多个建议，如果可用到maxSuggestions value

参数：

input string （错误/无效的单词我们需要纠正）
language string （用于搜索中的语言）
maxDistance number ，可选，默认值= 2（建议的最大距离）
maxSuggestions number ，可选，default = 5（要返回的最大建议编号）

返回：Array<Suggetion>建议数组

示例

await symSpellEx.search('argoments', 'en');

示例Suggestion Object：

{
  "term": "argoments",
  "suggestion": "arguments",  
  "distance": 2,
  "frequency": 155
}

更正

correct功能可用于以编辑距离和频率

来获取输入单词或句子的最佳建议

参数：

input string （错误/无效的单词我们需要纠正）
language string （要在搜索中使用的语言）
maxDistance number ，可选，默认值= 2（建议的最大距离）

返回：Correction包含原始input并更正的output字符串，带有一系列建议

示例

await symSpellEx.correct('Special relatvity was orignally proposed by Albert Einstein', 'en');

返回此Correction对象：

此输出完全取决于被推入商店的培训数据的质量

{
  "suggestions": [],
  "input": "Special relatvity was orignally proposed by Albert Einstein",
  "output": "Special relativity was originally proposed by Albert Einstein"
}

GitHub存储库

https://github.com/m-elbably/symspell-ex

结论

拼写检查是软件应用程序中广泛使用的功能。简单的拼写检查算法效率不高，可能会很慢。

有许多流行的编辑距离算法，例如Levenshtein距离，Damerau-Levenshtein距离，Jaro距离和Jaro-Winkler距离。

天真的方法涉及检查字典中的每个单词，以找到与拼写错误的单词最小的编辑距离的单词，这在计算上很昂贵。

Peter Norvig算法是一种拼写检查算法，它以与查询术语的给定编辑距离生成所有可能的术语，并在字典中搜索它们以找到正确的拼写。

对称删除拼写校正算法简化了仅通过使用删除作为操作来生成可能的拼写和搜索的过程，从而使其更快且无关紧要。

。

介绍