javascript - 模糊字符串搜索但针对对象？

Question

有很多库提供模糊字符串搜索功能，您可以在其中给出输入字符串，然后搜索“足够接近”的字符串。

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

• 猫(100%)
• 帽子
• 老鼠
• 猫
• 等等

除了对象之外，还有什么功能吗？一种算法，它采用两个对象并比较不是它们是否相似(这很简单并且已经完成)，而是比较它们的相似程度。相似度可以是从 0 到 100% 的百分比，其中 100% 是完全匹配，0% 根本不相似，也可以是一个数字，例如 https://en.wikipedia.org/wiki/Levenshtein_distance其中 0 表示完全匹配，数字表示“接近度”，没有上限。

例如，如果我有一个对象(javascript):

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

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

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

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

但是，与将 a 与 b 与完全不同的东西进行比较相比，比较 a 和 b 的结果会更接近，例如:

const c = {
  foo: 0
}

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

是否有任何现有的算法或库可以实现这样的目标？特别是在 JavaScript 中？

我发现了一些可能与此类似的库，但加上了我的批评:

• https://github.com/hath995/fuzzyEqual (javascript，似乎已经过时并且可能效率不高)
• https://github.com/intuit/fuzzy-matcher (java，看起来质量很高，但仅限于java)

Answer 1

如果对象最终由可序列化的值组成(没有类实例或函数)，一种选择是将它们字符串化，然后对这些字符串使用相同类型的“模糊搜索”算法:

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));