Wyszukiwanie rozmyte JavaScript, które ma sens

104

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.

willlma
źródło
Świetne pytanie. Chcę zrobić coś podobnego, ale z tymi samymi względami dotyczącymi porównania ciągów. Czy kiedykolwiek znalazłeś / zbudowałeś implementację javascript swoich porównań ciągów? Dzięki.
Nicholas
1
@nicholas Po prostu rozwidliłem fuzzyset.js na github, aby uwzględnić mniejsze ciągi zapytań i chociaż nie uwzględnia on operacji na ciągach ważonych, wyniki są całkiem dobre dla mojego zamierzonego zastosowania uzupełniania ciągów. Zobacz repozytorium
willlma
Dzięki. Spróbuję tego. Znalazłem również tę funkcję porównywania ciągów: github.com/zdyn/jaro-winkler-js . Wydaje się, że też działa całkiem nieźle.
Nicholas
1
Spróbuj tego: subtexteditor.github.io/fuzzysearch.js
michaelday
1
@michaelday To nie uwzględnia literówek. W wersji demonstracyjnej wpisywanie krolenie powraca Final Fantasy V: Krile, chociaż bym chciał. Wymaga, aby wszystkie znaki w zapytaniu były obecne w tej samej kolejności w wyniku, co jest dość krótkowzroczne. Wydaje się, że jedynym sposobem na dobre wyszukiwanie rozmyte jest posiadanie bazy danych typowych literówek.
willlma

Odpowiedzi:

22

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ć:

Thomas W.
źródło
67

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}]

Farzher
źródło
4
Nie byłem zadowolony z Fuse.js i wypróbowałem Twoją bibliotekę - działa świetnie! Dobra robota :)
dave
1
Jedynym problemem z tą biblioteką, z jakim się spotkałem, jest to, że słowo jest kompletne, ale na przykład niepoprawnie napisane, jeśli poprawnym słowem było "XRP" i jeśli
szukałem
1
@PirateApp tak, nie zajmuję się błędami ortograficznymi (ponieważ wyszukiwanie Sublime nie działa). przyglądam się temu teraz, kiedy ludzie narzekają. możesz podać przykładowe przypadki użycia, w których wyszukiwanie kończy się niepowodzeniem jako problem na
githubie
3
Dla tych z Was, którzy zastanawiają się nad tą biblioteką, teraz zaimplementowano również sprawdzanie pisowni! Polecam tę bibliotekę nad fusejs i innymi
PirateApp
1
@ user4815162342 musisz sam go zakodować. sprawdź
Farzher
18

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

InternalFX
źródło
3
Dzięki, właśnie tego szukałem. Byłoby tylko lepiej, gdyby to był zwykły js;)
lucaswxp
1
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 (słowo1, słowo2) {if (słowo1.length> 0 && słowo2.length> 0) {var pairs1 = get_bigrams (słowo1); 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]) hit_count ++; }} if (trafienia> 0) return ((2,0 * trafienia) / suma); } return 0.0}
jaya
Jak to wykorzystać w obiektach, w których będziesz chciał szukać za pomocą kilku kluczy?
user3808307
Ma to kilka problemów: 1) Niedoważa znaki na początku i na końcu ciągu. 2) Porównania bigramów to O (n ^ 2). 3) Wynik podobieństwa może przekraczać 1 z powodu implementacji. To oczywiście nie ma sensu. Rozwiązuję wszystkie te problemy w mojej odpowiedzi poniżej.
MgSam
9

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);
}
Roi Dayan
źródło
Chociaż prawdopodobnie nie tego chcesz w większości przypadków, to właśnie dla mnie.
schmijos,
Czy możesz zignorować zamówienie? fuzzyMatch('c a', 'a b c')powinien powrócićtrue
vsync
5

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"]
Jurij Sołowjow
źródło
Odniosłem również sukces z biblioteką Atom, która ma proste API i błyskawicznie =). github.com/cliffordfajardo/cato
cacoder
2

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.

David John Coleman II
źródło
Ten projekt jest rozdęty ( > 100kb) i zawiera dużą liczbę nieobsadzonych problemów i PR. Nie użyłbym tego z tych dwóch powodów.
vsync
2

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
}
jaya
źródło
2

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

MgSam
źródło
0
(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/

gość271314
źródło
0

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 .


źródło