模糊字符串搜索但对象？

Question

有很多库提供模糊字符串搜索功能，您可以在其中提供输入字符串，然后搜索 "close enough" 个字符串。

例如，如果您输入单词 cat，您可能会得到：

猫 (100%)
帽子
大鼠
猫
等等

是否有任何类型的功能，但对象？一种算法，它接受两个对象并比较不是它们是否相似（这很简单并且已经完成），而是而是它们有多相似 .从 0 到 100% 的百分比有多相似，其中 100% 是完全匹配，0% 完全不相似，或者它可以是一个数字，例如 https://en.wikipedia.org/wiki/Levenshtein_distance，其中 0 将是完全匹配，并且数字将是 "closeness"，没有上限。

例如，如果我有一个对象（java脚本）：

const a = {
  name: 'John Doe',
  age: 18
}

如果我将它与另一个对象进行比较：

const b = {
  name: 'Some random name',
  age: 5
}

你会得到一些不会是 0 的分数。我不确定你会得到什么值，这取决于你使用的评分系统（0-100% 或 x >= 0 )

但是，与将 a 与 b 进行比较的结果相比，将其与完全不同的事物进行比较，例如：

const c = {
  foo: 0
}

这里的对象几乎一点都不相似。所以这里的分数会更差（对于0-100%，它会是一个较低的数字，对于x>=0，它会是一个更高的数字，比起a比b）。

是否有任何现有的算法或库可以实现类似的功能？特别是在 javascript?

我发现了一些可能与此类似的库，但我补充了一些评论：

https://github.com/hath995/fuzzyEqual（java脚本，似乎过时且效率可能不高）
https://github.com/intuit/fuzzy-matcher（java，看起来质量很高，但只适用于java）

Answer 1

如果对象最终由可序列化的值组成（没有 class 实例或函数），一种选择是将它们字符串化，然后对这些字符串使用相同类型的 "fuzzy search" 算法：

const a = {
  name: 'John Doe',
  age: 18
};
const b = {
  name: 'Some random name',
  age: 5
};
const c = {
  foo: 0
};

// https://gist.github.com/andrei-m/982927
const getEditDistance = ((t,n)=>{if(0==t.length)return n.length;if(0==n.length)return t.length;var h,e,r=[];for(h=0;h<=n.length;h++)r[h]=[h];for(e=0;e<=t.length;e++)r[0][e]=e;for(h=1;h<=n.length;h++)for(e=1;e<=t.length;e++)n.charAt(h-1)==t.charAt(e-1)?r[h][e]=r[h-1][e-1]:r[h][e]=Math.min(r[h-1][e-1]+1,Math.min(r[h][e-1]+1,r[h-1][e]+1));return r[n.length][t.length]});
const diff = (obj1, obj2) => {
  const str1 = JSON.stringify(obj1);
  const str2 = JSON.stringify(obj2);
  const dist = getEditDistance(str1, str2);
  const peakDist = Math.max(str1.length, str2.length);
  return (peakDist - dist) / peakDist;
}
console.log(diff(b, b));
console.log(diff(b, a));
console.log(diff(b, c));

如果您只想比较 对象形状 ，而不是基础值，您可以在调用 JSON.stringify 时使用替换函数将所有原始值替换为空字符串。例如，您的 a 和 b 对象都将变为 {"name":"","age":""}，但您的 c 对象将变为 {"foo":""}.

const a = {
  name: 'John Doe',
  age: 18
};
const b = {
  name: 'Some random name',
  age: 5
};
const c = {
  foo: 0
};

// https://gist.github.com/andrei-m/982927
const getEditDistance = ((t,n)=>{if(0==t.length)return n.length;if(0==n.length)return t.length;var h,e,r=[];for(h=0;h<=n.length;h++)r[h]=[h];for(e=0;e<=t.length;e++)r[0][e]=e;for(h=1;h<=n.length;h++)for(e=1;e<=t.length;e++)n.charAt(h-1)==t.charAt(e-1)?r[h][e]=r[h-1][e-1]:r[h][e]=Math.min(r[h-1][e-1]+1,Math.min(r[h][e-1]+1,r[h-1][e]+1));return r[n.length][t.length]});
const stringify = obj => JSON.stringify(obj, (key, val) => (
  typeof val === 'object' && val !== null
    ? val
    : ''
));
const diff = (obj1, obj2) => {
  const str1 = stringify(obj1);
  const str2 = stringify(obj2);
  const dist = getEditDistance(str1, str2);
  const peakDist = Math.max(str1.length, str2.length);
  return (peakDist - dist) / peakDist;
}
console.log(diff(b, b));
console.log(diff(b, a));
console.log(diff(b, c));

模糊字符串搜索但对象？

Fuzzy String search but for objects?

javascript

algorithm

fuzzy-search