Wyszukiwanie rozmyte JavaScript, które ma sens

Szukam rozmytej biblioteki wyszukiwania JavaScript do filtrowania tablicy. Próbowałem używać fuzzyset.js i fuse.js , ale wyniki są straszne (są wersje demonstracyjne, które możesz wypróbować na połączonych stronach).

Po przeczytaniu informacji o odległości Levenshteina, wydaje mi się, że jest to słabe przybliżenie tego, czego szukają użytkownicy podczas pisania. Dla tych, którzy nie wiedzą, system oblicza, ile wstawień , usunięć i podstawień jest potrzebnych, aby dopasować dwa ciągi.

Oczywistą wadą, która jest zamocowana na modelu Levenshteina-Demerau jest to, że zarówno Blub i cycek są traktowane jednakowo podobny do bańki (każde wymaga dwie zmiany). Widać jednak, że żarówka bardziej przypomina blub niż boob , a model, o którym właśnie wspomniałem, rozpoznaje to, dopuszczając transpozycje .

Chcę tego użyć w kontekście uzupełniania tekstu, więc jeśli mam tablicę ['international', 'splint', 'tinder'], a moje zapytanie to int , myślę, że international powinno mieć wyższą rangę niż szyna , mimo że ta pierwsza ma wynik (wyższy = gorszy) 10 w porównaniu do tego ostatniego 3.

Więc to, czego szukam (i utworzę, jeśli nie istnieje), to biblioteka, która wykonuje następujące czynności:

• Waży różne manipulacje tekstem
• Waży każdą manipulację inaczej w zależności od tego, gdzie pojawiają się w słowie (wczesne manipulacje są droższe niż późne manipulacje)
• Zwraca listę wyników posortowanych według trafności

Czy ktoś spotkał coś takiego? Zdaję sobie sprawę, że StackOverflow nie jest miejscem, w którym można prosić o zalecenia dotyczące oprogramowania, ale ukryte (już nie!) W powyższym brzmi: czy myślę o tym we właściwy sposób?

Edytować

Znalazłem dobry artykuł (pdf) na ten temat. Kilka uwag i fragmentów:

Funkcje afinicznej odległości edycji przypisują relatywnie mniejszy koszt sekwencji wstawień lub usunięć

funkcja odległości Mongera-Elkana (Monge i Elkan 1996), która jest afinicznym wariantem funkcji odległości Smitha-Watermana (Durban et al. 1998) o określonych parametrach kosztowych

Dla odległości Smitha-Watermana (wikipedia) : „Zamiast patrzeć na całkowitą sekwencję, algorytm Smitha-Watermana porównuje segmenty o wszystkich możliwych długościach i optymalizuje miarę podobieństwa”. To podejście n-gramowe.

Zasadniczo podobną metryką, która nie jest oparta na modelu odległości edycji, jest metryka Jaro (Jaro 1995; 1989; Winkler 1999). W literaturze na temat łączenia rekordów dobre wyniki uzyskano przy zastosowaniu wariantów tej metody, opartej na liczbie i kolejności wspólnych znaków między dwoma ciągami.

Odmiana tego ze względu na Winklera (1999) wykorzystuje również długość P najdłuższego wspólnego przedrostka

(wydaje się być przeznaczony głównie do krótkich strun)

Do celów uzupełniania tekstu najbardziej sensowne wydają się podejścia Monger-Elkan i Jaro-Winkler. Dodatek Winklera do metryki Jaro efektywniej waży początki słów. A afiniczny aspekt Monger-Elkan oznacza, że ​​konieczność dokończenia słowa (będącego po prostu sekwencją dodatków) nie będzie go zbytnio nie podobać.

Wniosek:

ranking TFIDF wypadł najlepiej spośród kilku metryk odległości opartych na tokenach, a dostrojona metryka odległości edycji z przerwami afinicznymi zaproponowana przez Monge i Elkana uzyskała najlepsze wyniki spośród kilku metryk długości edycji. Zaskakująco dobrym miernikiem odległości jest szybki schemat heurystyczny, zaproponowany przez Jaro, a później rozszerzony przez Winklera. Działa to prawie tak samo dobrze jak schemat Monge-Elkana, ale jest o rząd wielkości szybsze. Jednym prostym sposobem połączenia metody TFIDF i Jaro-Winklera jest zastąpienie dokładnych dopasowań tokenów używanych w TFIDF przybliżonymi dopasowaniami tokenów opartymi na schemacie Jaro-Winklera. Ta kombinacja działa średnio nieco lepiej niż Jaro-Winkler lub TFIDF, a czasami działa znacznie lepiej. Jego wydajność jest również zbliżona do wyuczonej kombinacji kilku najlepszych wskaźników rozważanych w tym artykule.

Dobre pytanie! Ale myślę, że zamiast próbować modyfikować Levenshtein-Demerau, lepiej byłoby wypróbować inny algorytm lub połączyć / zważyć wyniki z dwóch algorytmów.

Wydaje mi się, że dokładne lub bliskie dopasowania do „początkowego przedrostka” to coś, czemu Levenshtein-Demerau nie przywiązuje szczególnej wagi - ale Twoje pozorne oczekiwania użytkowników tak.

Szukałem „lepszego niż Levenshtein” i znalazłem między innymi:

http://www.joyofdata.de/blog/comparison-of-string-distance-algorithms/

Wspomina się tu o wielu miarach „odległości struny”. Trzy, które wydawały się szczególnie istotne dla twojego wymagania, to:

1. Najdłuższa wspólna odległość podłańcucha: minimalna liczba symboli, które należy usunąć z obu ciągów, aż powstałe podciągi będą identyczne.

2. Odległość q-gram: Suma bezwzględnych różnic między wektorami N-gramowymi obu łańcuchów.

3. Odległość Jaccarda: 1 minuta stanowi iloraz wspólnych N-gramów i wszystkich obserwowanych N-gramów.

Może mógłbyś użyć ważonej kombinacji (lub minimum) tych wskaźników, z Levenshteinem - wspólny podciąg, wspólny N-gram lub Jaccard będą zdecydowanie preferować podobne ciągi - lub może spróbować po prostu użyć Jaccard?

W zależności od rozmiaru listy / bazy danych algorytmy te mogą być umiarkowanie drogie. W przypadku wyszukiwania rozmytego, które zaimplementowałem, użyłem konfigurowalnej liczby N-gramów jako „kluczy pobierania” z bazy danych, a następnie wykonałem kosztowną miarę odległości łańcucha, aby posortować je w kolejności preferencji.

Napisałem kilka uwag na temat wyszukiwania rozmytych ciągów w języku SQL. Widzieć:

• http://literatejava.com/sql/fuzzy-string-search-sql/

Próbowałem użyć istniejących rozmytych bibliotek, takich jak fuse.js, i również uznałem je za straszne, więc napisałem taką, która zachowuje się w zasadzie jak wyszukiwanie sublime. https://github.com/farzher/fuzzysort

Jedyną literówką, na jaką pozwala, jest transpozycja. Jest całkiem solidny (1k gwiazdek, 0 problemów) , bardzo szybki i łatwo radzi sobie z Twoją sprawą:

fuzzysort.go('int', ['international', 'splint', 'tinder'])
// [{highlighted: '*int*ernational', score: 10}, {highlighted: 'spl*int*', socre: 3003}]

Oto technika, której użyłem kilka razy ... Daje całkiem niezłe rezultaty. Jednak nie robi wszystkiego, o co prosiłeś. Ponadto może to być kosztowne, jeśli lista jest ogromna.

get_bigrams = (string) ->
    s = string.toLowerCase()
    v = new Array(s.length - 1)
    for i in [0..v.length] by 1
        v[i] = s.slice(i, i + 2)
    return v

string_similarity = (str1, str2) ->
    if str1.length > 0 and str2.length > 0
        pairs1 = get_bigrams(str1)
        pairs2 = get_bigrams(str2)
        union = pairs1.length + pairs2.length
        hit_count = 0
        for x in pairs1
            for y in pairs2
                if x is y
                    hit_count++
        if hit_count > 0
            return ((2.0 * hit_count) / union)
    return 0.0

Przekaż dwa ciągi, do string_similarityktórych zwróci liczbę między 0iw 1.0zależności od tego, jak są podobne. W tym przykładzie zastosowano Lo-Dash

Przykład użycia ...

query = 'jenny Jackson'
names = ['John Jackson', 'Jack Johnson', 'Jerry Smith', 'Jenny Smith']

results = []
for name in names
    relevance = string_similarity(query, name)
    obj = {name: name, relevance: relevance}
    results.push(obj)

results = _.first(_.sortBy(results, 'relevance').reverse(), 10)

console.log results

Poza tym .... mieć skrzypce

Upewnij się, że konsola jest otwarta lub nic nie zobaczysz :)

to jest moja krótka i kompaktowa funkcja do dopasowania rozmytego:

function fuzzyMatch(pattern, str) {
  pattern = '.*' + pattern.split('').join('.*') + '.*';
  const re = new RegExp(pattern);
  return re.test(str);
}

możesz rzucić okiem na https://github.com/atom/fuzzaldrin/ Atom's lib .

jest dostępny na npm, ma proste API i dla mnie działał dobrze.

> fuzzaldrin.filter(['international', 'splint', 'tinder'], 'int');
< ["international", "splint"]

Aktualizacja z listopada 2019 r. Odkryłem, że bezpiecznik ma całkiem przyzwoite ulepszenia. Jednak nie mogłem go zmusić do korzystania z bool's (tj. Operatorów OR, AND itp.), Ani nie mogłem użyć interfejsu wyszukiwania API do filtrowania wyników.

Odkryłem nextapps-de/flexsearch: https://github.com/nextapps-de/flexsearch i uważam, że zdecydowanie przewyższa wiele innych bibliotek wyszukiwania javascript, które wypróbowałem, i ma wsparcie bool, filtrowanie wyszukiwania i paginację.

Możesz wprowadzić listę obiektów javascript dla swoich danych wyszukiwania (tj. Pamięci), a API jest dość dobrze udokumentowane: https://github.com/nextapps-de/flexsearch#api-overview

Do tej pory zindeksowałem blisko 10 000 rekordów, a moje wyszukiwania są niemal natychmiastowe; tj. niezauważalna ilość czasu na każde wyszukiwanie.

tutaj jest rozwiązanie dostarczone przez @InternalFX, ale w JS (użyłem go więc udostępniając):

function get_bigrams(string){
  var s = string.toLowerCase()
  var v = s.split('');
  for(var i=0; i<v.length; i++){ v[i] = s.slice(i, i + 2); }
  return v;
}

function string_similarity(str1, str2){
  if(str1.length>0 && str2.length>0){
    var pairs1 = get_bigrams(str1);
    var pairs2 = get_bigrams(str2);
    var union = pairs1.length + pairs2.length;
    var hits = 0;
    for(var x=0; x<pairs1.length; x++){
      for(var y=0; y<pairs2.length; y++){
        if(pairs1[x]==pairs2[y]) hits++;
    }}
    if(hits>0) return ((2.0 * hits) / union);
  }
  return 0.0
}

Naprawiłem problemy z rozwiązaniem bigramu CoffeeScript firmy InternalFx i uczyniłem z niego ogólne rozwiązanie n-gramowe (możesz dostosować rozmiar gramów).

To jest TypeScript, ale możesz usunąć adnotacje typu i działa również dobrze jako zwykły JavaScript.

/**
 * Compares the similarity between two strings using an n-gram comparison method. 
 * The grams default to length 2.
 * @param str1 The first string to compare.
 * @param str2 The second string to compare.
 * @param gramSize The size of the grams. Defaults to length 2.
 */
function stringSimilarity(str1: string, str2: string, gramSize: number = 2) {
  function getNGrams(s: string, len: number) {
    s = ' '.repeat(len - 1) + s.toLowerCase() + ' '.repeat(len - 1);
    let v = new Array(s.length - len + 1);
    for (let i = 0; i < v.length; i++) {
      v[i] = s.slice(i, i + len);
    }
    return v;
  }

  if (!str1?.length || !str2?.length) { return 0.0; }

  //Order the strings by length so the order they're passed in doesn't matter 
  //and so the smaller string's ngrams are always the ones in the set
  let s1 = str1.length < str2.length ? str1 : str2;
  let s2 = str1.length < str2.length ? str2 : str1;

  let pairs1 = getNGrams(s1, gramSize);
  let pairs2 = getNGrams(s2, gramSize);
  let set = new Set<string>(pairs1);

  let total = pairs2.length;
  let hits = 0;
  for (let item of pairs2) {
    if (set.delete(item)) {
      hits++;
    }
  }
  return hits / total;
}

Przykłady:

console.log(stringSimilarity("Dog", "Dog"))
console.log(stringSimilarity("WolfmanJackIsDaBomb", "WolfmanJackIsDaBest"))
console.log(stringSimilarity("DateCreated", "CreatedDate"))
console.log(stringSimilarity("a", "b"))
console.log(stringSimilarity("CreateDt", "DateCreted"))
console.log(stringSimilarity("Phyllis", "PyllisX"))
console.log(stringSimilarity("Phyllis", "Pylhlis"))
console.log(stringSimilarity("cat", "cut"))
console.log(stringSimilarity("cat", "Cnut"))
console.log(stringSimilarity("cc", "Cccccccccccccccccccccccccccccccc"))
console.log(stringSimilarity("ab", "ababababababababababababababab"))
console.log(stringSimilarity("a whole long thing", "a"))
console.log(stringSimilarity("a", "a whole long thing"))
console.log(stringSimilarity("", "a non empty string"))
console.log(stringSimilarity(null, "a non empty string"))

Wypróbuj to na placu zabaw TypeScript

(function (int) {
    $("input[id=input]")
        .on("input", {
        sort: int
    }, function (e) {
        $.each(e.data.sort, function (index, value) {
          if ( value.indexOf($(e.target).val()) != -1 
              && value.charAt(0) === $(e.target).val().charAt(0) 
              && $(e.target).val().length === 3 ) {
                $("output[for=input]").val(value);
          };
          return false
        });
        return false
    });
}(["international", "splint", "tinder"]))

jsfiddle http://jsfiddle.net/guest271314/QP7z5/

Sprawdź mój dodatek do Arkuszy Google o nazwie Flookup i użyj tej funkcji:

Flookup (lookupValue, tableArray, lookupCol, indexNum, threshold, [rank])

Szczegóły parametru to:

1. lookupValue: wartość, na którą patrzysz
2. tableArray: tabela, którą chcesz przeszukać
3. lookupCol: kolumna, którą chcesz przeszukać
4. indexNum: kolumna, z której mają zostać zwrócone dane
5. threshold: procentowe podobieństwo, poniżej którego dane nie powinny być zwracane
6. rank: n-te najlepsze dopasowanie (tj. jeśli pierwsze dopasowanie nie odpowiada Twoim upodobaniom)

To powinno spełnić twoje wymagania ... chociaż nie jestem pewien co do punktu numer 2.

Dowiedz się więcej na oficjalnej stronie internetowej .