regex - JavaScript uskarp søk som gir mening

Jeg leter etter et fuzzy search JavaScript-bibliotek for å filtrere et array. Jeg har prøvd å bruke fuzzyset.js og fuse.js, men resultatene er dårlige (det finnes demoer du kan prøve på de lenkede sidene).

Etter å ha gjort litt lesing om Levenshtein-avstand, slår det meg som en dårlig tilnærming til hva brukere leter etter når de skriver. For de som ikke vet det, beregner systemet hvor mange innsettinger, slettinger og erstatninger som trengs for å få to strenger til å stemme overens.

En åpenbar feil, som er rettet i Levenshtein-Demerau-modellen, er at både blub og boob anses som like like bulb (hver krever to substitusjoner). Det er imidlertid klart at bulb er mer lik blub enn boob er, og modellen jeg nettopp nevnte anerkjenner dette ved å tillate transposisjoner.

Jeg vil bruke dette i konteksten av tekstfullføring, så hvis jeg har et array ['international', 'splint', 'tinder'], og min forespørsel er int, synes jeg international burde rangere høyere enn splint, selv om førstnevnte har en poengsum (høyere=verre) på 10 mot sistnevntes 3.

Så det jeg ser etter (og vil lage hvis det ikke eksisterer), er et bibliotek som gjør følgende:

  • Vekter de forskjellige tekstmanipulasjonene
  • Vekter hver manipulering forskjellig avhengig av hvor de vises i et ord (tidlige manipuleringer er mer kostbare enn sene manipuleringer)
  • Returnerer en liste over resultater sortert etter relevans

Har noen kommet over noe som dette? Jeg innser at Stack Overflow ikke er stedet å spørre om programvareanbefalinger, men implisitt (ikke lenger!) i det ovenstående er: tenker jeg på dette på riktig måte?

Rediger

Jeg fant en god artikkel (pdf) om emnet. Noen notater og utdrag:

Affine redigerings-avstand funksjoner tilordner en relativt lavere kostnad til en rekke innsettinger eller slettinger

Monger-Elkan-avstandsfunksjonen (Monge & Elkan 1996), som er en affinvariant av Smith-Waterman-avstandsfunksjonen (Durban et al. 1998) med bestemte kostnadsparametere

For Smith-Waterman-avstanden (Wikipedia), "I stedet for å se på hele sekvensen, sammenligner Smith-Waterman-algoritmen segmenter av alle mulige lengder og optimaliserer likhetsmålingen." Det er n-gram-tilnærmingen.

En bredt liknende metrikk, som ikke er basert på en redigeringsavstandmodell, er Jaro-metrikken (Jaro 1995; 1989; Winkler 1999). I litteraturen om registerkobling har gode resultater blitt oppnådd ved bruk av varianter av denne metoden, som er basert på antall og rekkefølge av de felles tegnene mellom to strenger.

En variant av dette på grunn av Winkler (1999) bruker også lengden P av den lengste felles prefiksen

(ser ut til å være ment først og fremst for korte strenger)

For tekstfullføringsformål ser det ut til at Monger-Elkan- og Jaro-Winkler-tilnærmingene gir mest mening. Winklers tillegg til Jaro-metrikken vektlegger effektivt begynnelsen av ord mer. Og den affine aspekten ved Monger-Elkan betyr at nødvendigheten av å fullføre et ord (som rett og slett er en sekvens av tillegg) ikke vil mislike det for mye.

Konklusjon:

TFIDF-rangeringen presterte best blant flere token-baserte distansemetoder, og en justert affine-gap redigeringsdistansemetode foreslått av Monge og Elkan presterte best blant flere strengredigeringsdistansemetoder. En overraskende god distansemetode er en rask heuristisk ordning, foreslått av Jaro og senere utvidet av Winkler.

Dette fungerer nesten like godt som Monge-Elkan-ordningen, men er en størrelsesorden raskere. En enkel måte å kombinere TFIDF-metoden og Jaro-Winkler på er å erstatte nøyaktige token-tilfeller brukt i TFIDF med omtrentlige token-tilfeller basert på Jaro-Winkler-ordningen. Denne kombinasjonen gir litt bedre ytelse enn enten Jaro-Winkler eller TFIDF i gjennomsnitt, og av og til gir den mye bedre ytelse. Den er også nærme i ytelse til en lært kombinasjon av flere av de beste metrikkene som vurderes i denne artikkelen.

Svar #1

Jeg prøvde å bruke eksisterende fuzzy-biblioteker som fuse.js og fant dem også forferdelige, så jeg skrev et som oppfører seg omtrent som Sublimes søk. https://github.com/farzher/fuzzysort

Den eneste skrivefeilen den tillater er en ombytting. Den er ganske solid (1k stjerner, 0 problemer), veldig rask, og håndterer saken din enkelt:

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

Svar #2

Godt spørsmål! Men jeg tenker at i stedet for å prøve å endre Levenshtein-Demerau, kan det være bedre å prøve en annen algoritme eller kombinere/vekte resultatene fra to algoritmer.

Det slår meg at eksakte eller nærme treff på «startprefikset» er noe Levenshtein-Demerau ikke gir noen spesiell vekt, men dine åpenbare brukerforventninger ville gjøre det.

Jeg søkte etter "bedre enn Levenshtein" og fant, blant annet, dette:

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

Dette nevner en rekke "strengavstand"-målinger. Tre som virket spesielt relevante for ditt krav, ville være:

  1. Lengste felles delstrengavstand: Minimum antall symboler som må fjernes i begge strengene til de resulterende delstrengene er identiske.

  2. q-gram-avstand: Summen av absolutte forskjeller mellom N-gram-vektorene til begge strengene.

  3. Jaccard-avstand: 1 minus kvotienten av delte N-grammer og alle observerte N-grammer.

Kanskje du kunne bruke en vektet kombinasjon (eller minimum) av disse metrikkene, med Levenshtein -- vanlig delstreng, vanlig N-gram eller Jaccard vil alle sterkt foretrekke lignende strenger -- eller kanskje prøve bare å bruke Jaccard?

Avhengig av størrelsen på listen/databasen din, kan disse algoritmene være moderat kostbare. For et fuzzy-søk jeg implementerte, brukte jeg et konfigurerbart antall N-grammer som "hentingsnøkler" fra databasen, og deretter kjørte jeg den kostbare strengavstandsmålingen for å sortere dem i foretrukket rekkefølge.

Jeg skrev noen notater om fuzzysøk i SQL. Se:

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

Svar #3

dette er min korte og kompakte funksjon for uskarp matching:

function escapeRegExp(str: string) {
  return str.replace(/[.*+?^${}()|[\]\\]/g, '\\$&');
}

function fuzzyMatch(pattern, str) {
  pattern = '.*' + pattern.split('').map(l => `${escapeRegExp(l)}.*`).join('');
  const re = new RegExp(pattern);
  return re.test(str);
}

takket være jt3k, har jeg oppdatert funksjonen for å escape regex

escapeRegExp som foreslått på MDN Docs

Svar #4

Her er en teknikk jeg har brukt noen ganger... Den gir ganske gode resultater. Gjør imidlertid ikke alt du ba om. Dette kan også bli dyrt hvis listen er enorm.

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

Pass to strenger til string_similarity som vil returnere et tall mellom 0 og 1.0 avhengig av hvor like de er. Dette eksemplet bruker Lo-Dash

Brukseksempel....

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

Også....ta en prøve

Sørg for at konsollen din er åpen, ellers vil du ikke se noe :)

Svar #5

Jeg har fikset problemene med CoffeeScript-bigramløsningen av InternalFx og gjort det til en generell n-gram-løsning (du kan tilpasse størrelsen på grammene).

Dette er TypeScript, men du kan fjerne typeannotasjonene, og det fungerer fint som vanlig JavaScript også.

/**
 * 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;
}

Eksempler:

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

Prøv det i TypeScript-lekeplassen

Relaterte artikler