JavaScript如何通过与字符串匹配来对数组进行排序

Question

我有一个包含地理位置代码结果的数组。我想按照与我搜索的词最接近的匹配来对其进行排序。 例如，搜索：“Pizza”。

Array: Pizza Uno, Pizzeria Uno, Burgers and Pizzeria, Cino Pizzeria. 

排好序的数组应该是：

Pizza Uno,
Pizzeria Uno,
Burgers and Pizzeria,
Cino Pizzeria. 

感谢您的帮助。

- Leonardo Amigoni

---

你需要描述一下你想用来确定“最接近”的算法。显然，完美匹配可以是最高的，但是是什么决定了其他三个具有相同部分匹配的项目的顺序呢？ - jfriend00

为什么“汉堡和比萨饼店”比“Cino Pizzeria”更接近于“Pizza”？ - Mark Byers

好问题。我不知道最好的算法是什么。我想匹配搜索字符串，然后按字母顺序显示相同匹配项。这就是为什么Burgers和Pizzeria比Cino Pizzeria更接近。相同的匹配但按字母顺序更高。 - Leonardo Amigoni

Answer 1

一个非常基础的算法，是根据匹配字符串占总字符串长度的百分比进行排序。所以，“Pizza”的完全匹配将是5/5（100％），而“Pizza Uno”的匹配将是5/9，“Pizzeria Uno”则是4/12，等等。这是MySQL自然排序算法最基本的核心组成部分之一。

- Rylab

---

谢谢您的回答。这是一个非常有趣的方法。我该如何在Javascript中实现它呢？我不能直接访问谷歌地点数据库，所以我必须自己对结果进行排序。 - Leonardo Amigoni

Answer 2

这个怎么样？这是我第一次尝试根据十六进制颜色获取最接近的颜色名称的方法。

当然，还有更好的解决方案。例如，您可以查看sift算法，它比levenshtein的方法要快得多。

但是这应该能按照您的期望工作。

Array.closest = (function () {
    function levenshtein(s, t) {
        if (!s.length) return t.length;
        if (!t.length) return s.length;

        return Math.min(
            levenshtein((s.substring(1), t) + 1,
            levenshtein((t.substring(1), s) + 1,
            levenshtein((s.substring(1), t.substring(1)) + (s[0] !== t[0] ? 1 : 0)
        );
    }

    return function (arr, str) {
        return arr.sort(function (a, b) {
            return levenshtein((a, str) - levenshtein((b, str);
        });
    };
}());


var arr = ['Pizza Uno', 'Pizzeria Uno', 'Burgers and Pizzeria', 'Cino Pizzeria.'];
Array.closest(arr, 'Pizza') // => ['Pizza Uno', 'Pizzeria Uno', 'Cino Pizzeria.', 'Burgers and Pizzeria'];

- yckart

---

有两个问题：函数中存在大量的括号错误和使用 'substring(1)' 的逻辑错误。 substring(1) 只返回任何字符串提供的第二个字符。我无法确定你的意思是 'substring(0)' [第一个字符] 还是其他什么，但这个函数无论如何都不能按预期工作。 - Evan

如果数组长度超过10到15个元素，这会非常慢。这也会在每次比较（a-b）（a-c）（a-d）中重新计算Levenshtein距离。 - kaiser

Answer 3

你可以尝试计算两个字符串之间的Levenshtein Distance。它基本上是使两个字符串相同所需的步骤数。

- Pierre

---

谢谢您的建议。这似乎让我更接近目标了。 - Leonardo Amigoni