关于算法:命令行错误提示谈谈模糊集

命令行谬误提醒—谈谈模糊集

在开发的过程中，咱们会应用各种指令。有时候，咱们因为这样或者那样的起因，写错了某些指令。此时，应用程序往往会爆出谬误。

Unrecognized option ‘xxx’ (did you mean ‘xxy’?)
能够看到，以后代码不仅仅提醒了以后你输出的配置谬误。同时还提供了相似以后输出的近似匹配指令。十分的智能。此时，咱们须要应用算法来计算，即模糊集。
事实上，模糊集其实能够解决一些事实的问题。例如咱们有一个“高个子”汇合 A，定义 1.75m 为高个子。那么在通用逻辑中咱们会认为某一个元素附属或者不附属该汇合。也就是 1.78 就是高个子，而 1.749 就不是高个子，即便它间隔 1.75 米只差里一毫米。该汇合被称为 (two-valued 二元集)，与此绝对的，含糊汇合则没有这种问题。
在含糊汇合中，所有人都是汇合 A 的成员，所不同的仅仅是匹配度而已。咱们能够通过计算匹配度来决定差异性。

如何运行

言归正转，咱们回到以后实现。对于模糊集的实现，咱们能够参考 fuzzyset.js (注: 该库须要商业许可) 和 fuzzyset.js 交互式文档 进行学习。
在这里，我仅仅只介绍根本算法，至于数据存储和优化在残缺实现中。
通过查看交互式文档，咱们能够算法是通过余弦类似度公式去计算。
在直角坐标系中，类似度公式如此计算。

cos = (a b) / (|a| |b| ). => 等同于

((x1, y1) (x2,y2)) / (Math.sqrt(x1 2 + y1 2) Math.sqrt(x2 2 + y2 2))
而类似度公式是通过将字符串转化为数字矢量来计算。如果以后的字符串别离为“smaller”和“smeller”。咱们须要合成字符串子串来计算。
以后能够合成的字符串子串能够依据我的项目来自行调整，简略起见，咱们这里应用 2 为单位。
两个字符串能够被合成为:

const smallSplit: string[] = ['-s', 'sm', 'ma', 'al', 'll', 'l-']
const smelllSplit: string[] = ['-s', 'sm', 'me', 'el', 'll', 'll', 'l-']

咱们能够依据以后把代码变为如下向量:

const smallGramCount = {'-s': 1, 'sm': 1, 'ma': 1, 'al': 1, 'll': 1, 'l-': 1}
const smallGramCount = {'-s': 1, 'sm': 1, 'me': 1, 'el': 1, 'll': 2, 'l-': 1}

const _nonWordRe = /[^a-zA-Z0-9u00C0-u00FF,]+/g;
/**
 * 能够间接把 'bal' 变为 ['-b', 'ba', 'al', 'l-'] */function iterateGrams (value: string, gramSize: number = 2) {// 以后 数值增加前后缀 '-' const simplified = '-' + value.toLowerCase().replace(_nonWordRe, '') +'-'
   // 通过计算以后子字符串长度和以后输出数据长度的差值
 const lenDiff = gramSize - simplified.length
   // 后果数组
 const results = []   // 如果以后输出的数据长度小于以后长度
 // 间接增加“-”补差计算 if (lenDiff > 0) {for (var i = 0; i < lenDiff; ++i) {value += '-';} }   // 循环截取数值并且塞入后果数组中
 for (var i = 0; i < simplified.length - gramSize + 1; ++i) {results.push(simplified.slice(i, i + gramSize));
 } return results;}
/**
 * 能够间接把 ['-b', 'ba', 'al', 'l-'] 变为 {-b: 1, 'ba': 1, 'al': 1, 'l-': 1} */function gramCounter(value: string, gramSize: number = 2) {const result = {} // 依据以后的 const grams = _iterateGrams(value, gramSize) for (let i = 0; i < grams.length; ++i) {// 依据以后是否有数据来进行数据减少和初始化 1 if (grams[i] in result) {result[grams[i]] += 1; } else {result[grams[i]] = 1; } } return result;}

而后咱们能够计算 small * smell 为:

function calcVectorNormal() {// 获取向量对象 const small_counts = gramCounter('small', 2) const smell_counts = gramCOunter('smell', 2)   // 应用 set 进行字符串过滤
 const keySet = new Set()
   // 把两单词组共有的字符串塞入 keySet
 for (let key in small_counts) {keySet.add(key)
 }   for (let key in smell_counts) {keySet.add(key)
 }   let sum: number = 0
   // 计算 small * smell
 for(let key in keySet.keys()) {sum += (small_count[key] ?? 0) * (smell_count[key] ?? 0) }   return sum
}

同时咱们能够计算 |small|*|smell| 为:

同理可得以后 smell sqrt 也是 2.449。
最终的计算为：4 / (2.449 * 2.449) = 0.66。
计算形式为

// ... 上述代码
function calcVectorNormal() {// 获取向量对象 const gram_counts = gramCounter(normalized_value, 2); // 计算 let sum_of_square_gram_counts = 0; let gram; let gram_count;
 for (gram in gram_counts) {gram_count = gram_counts[gram]; // 乘方相加 sum_of_square_gram_counts += Math.pow(gram_count, 2);
 }
 return Math.sqrt(sum_of_square_gram_counts);
}

则 small 与 smell 在子字符串为 2 状况下匹配度为 0.66。
当然，咱们看到结尾和完结增加了 – 也作为标识符号，该标识是为了辨认出 sell 与 llse 之间的不同，如果应用

const sellSplit = ['-s', 'se', 'el', 'll', 'l-']
const llseSplit = ['-l', 'll', 'ls', 'se', 'e-']

咱们能够看到以后的类似的只有 ‘ll’ 和 ‘se’ 两个子字符串。

残缺代码

编译型框架 svelte 我的项目代码中用到此性能，应用代码解析如下:

const valid_options = ['format', 'name', 'filename', 'generate', 'outputFilename', 'cssOutputFilename', 'sveltePath', 'dev', 'accessors', 'immutable', 'hydratable', 'legacy', 'customElement', 'tag', 'css', 'loopGuardTimeout', 'preserveComments', 'preserveWhitespace'];
// 如果以后操作不在验证项中，才会进行含糊匹配
if (!valid_options.includes(key)) {// 匹配后返回 match 或者 null const match = fuzzymatch(key, valid_options);
 let message = `Unrecognized option '${key}'`; if (match) message += ` (did you mean '${match}'?)`;
 throw new Error(message);
}

实现代码如下所示:

export default function fuzzymatch(name: string, names: string[]) {// 依据以后已有数据建设模糊集，如果有字符须要进行匹配、则能够对对象进行缓存 const set = new FuzzySet(names); // 获取以后的匹配 const matches = set.get(name);
 // 如果有匹配项，且匹配度大于 0.7，返回匹配单词，否则返回 null return matches && matches[0] && matches[0][0] > 0.7 ? matches[0][1] : null;}
// adapted from https://github.com/Glench/fuzzyset.js/blob/master/lib/fuzzyset.js
// BSD Licensed
// 最小子字符串 2
const GRAM_SIZE_LOWER = 2;// 最大子字符串 3
const GRAM_SIZE_UPPER = 3;
//  进行 Levenshtein 计算，更适宜输出残缺单词的匹配
function _distance(str1: string, str2: string) {if (str1 === null && str2 === null) throw 'Trying to compare two null values'; if (str1 === null || str2 === null) return 0; str1 = String(str1);
 str2 = String(str2);
 const distance = levenshtein(str1, str2);
 if (str1.length > str2.length) {return 1 - distance / str1.length;} else {return 1 - distance / str2.length;}}
// Levenshtein 间隔，是指两个字串之间，由一个转成另一个所需的起码的编辑操作次数。function levenshtein(str1: string, str2: string) {const current: number[] = []; let prev; let value;
 for (let i = 0; i <= str2.length; i++) {for (let j = 0; j <= str1.length; j++) {if (i && j) {if (str1.charAt(j - 1) === str2.charAt(i - 1)) {value = prev;} else {value = Math.min(current[j], current[j - 1], prev) + 1;
 } } else {value = i + j;} prev = current[j]; current[j] = value; } } return current.pop();}
// 正则匹配除单词 字母 数字以及逗号和空分外的数据
const non_word_regex = /[^w,]+/;
// 上述代码曾经介绍
function iterate_grams(value: string, gram_size = 2) {const simplified = '-' + value.toLowerCase().replace(non_word_regex, '') +'-';
 const len_diff = gram_size - simplified.length;
 const results = [];
 if (len_diff > 0) {for (let i = 0; i < len_diff; ++i) {value += '-';} } for (let i = 0; i < simplified.length - gram_size + 1; ++i) {results.push(simplified.slice(i, i + gram_size));
 } return results;}
// 计算向量，上述代码曾经介绍
function gram_counter(value: string, gram_size = 2) {const result = {};const grams = iterate_grams(value, gram_size);
 let i = 0;
 for (i; i < grams.length; ++i) {if (grams[i] in result) {result[grams[i]] += 1; } else {result[grams[i]] = 1; } } return result;}
// 排序函数
function sort_descending(a, b) {return b[0] - a[0];}
class FuzzySet {// 数据汇合，记录所有的可选我的项目 // 1. 优化初始化时候，雷同的可选项数据，同时防止屡次计算雷同向量 // 2. 以后输出的值与可选项相等，间接返回，无需计算 exact_set = {}; // 匹配对象存入，存储所有单词的向量 // 如 match_dist['ba'] = [//     第 2 个单词，有 3 个 //     {3, 1} //     第 5 个单词，有 2 个 //     {2, 4}  //   ]
 //   前面单词匹配时候，能够依据单词索引进行匹配而后计算最终分数 match_dict = {}; // 依据不同子字符串获取不同的单词向量，最终有不同的匹配度 // item[2] = [[2.6457513110645907, "aaab"]] items = {};
 constructor(arr: string[]) {// 以后抉择 2 和 3 为子字符串匹配 // item = {2: [], 3: []} for (let i = GRAM_SIZE_LOWER; i < GRAM_SIZE_UPPER + 1; ++i) {this.items[i] = [];}     // 增加数组
 for (let i = 0; i < arr.length; ++i) {this.add(arr[i]);
 } }
 add(value: string) {const normalized_value = value.toLowerCase();
     // 如果以后单词曾经计算，间接返回
 if (normalized_value in this.exact_set) {return false;}
 // 别离计算 2 和 3 的向量 for (let i = GRAM_SIZE_LOWER;; i < GRAM_SIZE_UPPER + 1; ++i) {this._add(value, i);
 } }
 _add(value: string, gram_size: number) {const normalized_value = value.toLowerCase();
 // 获取 items[2] const items = this.items[gram_size] || [];
 // 获取数组的长度作为索引 const index = items.length;
 // 没有看出有理论的用途？试验也没有什么作用？不会影响 items.push(0);
     // 获取 向量数据
 const gram_counts = gram_counter(normalized_value, gram_size);
 let sum_of_square_gram_counts = 0; let gram; let gram_count;
 // 同上述代码，只不过把所有的匹配我的项目和以后索引都退出 match_dict 中去 // 如 this.match_dict['aq'] = [[1, 2], [3,3]] for (gram in gram_counts) {gram_count = gram_counts[gram]; sum_of_square_gram_counts += Math.pow(gram_count, 2);
 if (gram in this.match_dict) {this.match_dict[gram].push([index, gram_count]);
 } else {this.match_dict[gram] = [[index, gram_count]];
 } } const vector_normal = Math.sqrt(sum_of_square_gram_counts);
 // 增加向量  如：this.items[2][3] = [4.323, 'sqaaaa'] items[index] = [vector_normal, normalized_value];    this.items[gram_size] = items;
 // 设置以后小写字母，优化代码 this.exact_set[normalized_value] = value;
 }
 // 输出以后值，获取选择项 get(value: string) {const normalized_value = value.toLowerCase();
 const result = this.exact_set[normalized_value];
 // 如果以后值齐全匹配，间接返回 1，不用计算 if (result) {return [[1, result]]; }
 let results = []; // 从多到少，如果多子字符串没有后果，转到较小的大小 for ( let gram_size = GRAM_SIZE_UPPER;
 gram_size >= GRAM_SIZE_LOWER;
 --gram_size ) {results = this.__get(value, gram_size);
 if (results) {return results;} } return null; }
 __get(value: string, gram_size: number) {const normalized_value = value.toLowerCase();
 const matches = {}; // 取得以后值的向量值 const gram_counts = gram_counter(normalized_value, gram_size);
 const items = this.items[gram_size];
 let sum_of_square_gram_counts = 0; let gram; let gram_count; let i; let index; let other_gram_count;
 // 计算失去较为匹配的数据 for (gram in gram_counts) {// 获取 向量单词用于计算 gram_count = gram_counts[gram]; sum_of_square_gram_counts += Math.pow(gram_count, 2);
 // 获得以后匹配的 [index，gram_count] if (gram in this.match_dict) {// 获取所有匹配以后向量单词的我的项目，并且依据 索引退出 matches for (i = 0; i < this.match_dict[gram].length; ++i) {// 取得以后匹配的索引 === 输出单词[index] index = this.match_dict[gram][i][0];
 // 取得匹配子字符串的值 other_gram_count = this.match_dict[gram][i][1];
 // 单词索引增加，注：只有和以后子字符串匹配的 索引都会退出 matches if (index in matches) {matches[index] += gram_count * other_gram_count; } else {matches[index] = gram_count * other_gram_count; } } } }  
 const vector_normal = Math.sqrt(sum_of_square_gram_counts);
 let results = []; let match_score;
 // 构建最终后果 [分数, 单词] for (const match_index in matches) {match_score = matches[match_index]; results.push([// 分数 match_score / (vector_normal * items[match_index][0]), // 单词 items[match_index][1] ]); }
 // 尽管所有的与之匹配子字符串都会进入，但咱们只须要最高的分数 results.sort(sort_descending);
 let new_results = [];     // 如果匹配数目很大，只取的前 50 个数据进行计算
 const end_index = Math.min(50, results.length);
     // 因为是字符类型数据，依据以后数据在此计算 levenshtein  间隔
 for (let i = 0; i < end_index; ++i) { new_results.push([_distance(results[i][1], normalized_value), results[i][1]
 ]);   }
 results = new_results; // 在此排序 results.sort(sort_descending);
 new_results = []; for (let i = 0; i < results.length; ++i) {// 因为 第一的分数是最高的，所有前面的数据如果等于第一个 // 也能够进入最终抉择 if (results[i][0] == results[0][0]) {new_results.push([results[i][0], this.exact_set[results[i][1]]]);
 } }
 // 返回最终后果 return new_results; }}

激励一下

如果你感觉这篇文章不错，心愿能够给与我一些激励，在我的 github 博客下帮忙 star 一下。
博客地址

参考资料

fuzzyset.js 交互式文档
svelte fuzzymatch