JavaScript fuzzy search, który ma sens

Próbowałem użyć istniejących bibliotek rozmytych, takich jak fuse.js, a także okazało się, że są straszne, więc napisałem jeden, który zachowuje się w zasadzie jak poszukiwania sublime. https://github.com/farzher/fuzzysort

Jedyną dopuszczalną literówką jest transpozycja. To całkiem solidne (1K stars, 0 issues), bardzo szybko i łatwo załatwia 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 times...It daje całkiem dobre wyniki. Nie robi jednak 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 znaków do string_similarity, które zwrócą liczbę pomiędzy 0 i 1.0 w zależności od tego, jak są podobne. Ten przykład używa 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

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

To jest moja krótka i zwarta funkcja dla dopasowania rozmytego:

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

Możesz spojrzeć na Atom https://github.com/atom/fuzzaldrin / lib.

Jest dostępny na npm, ma proste API i Działa ok dla mnie.

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

Aktualizacja Z Listopada 2019 R. Znalazłem bezpiecznik, który ma całkiem przyzwoite ulepszenia. Nie mogłem jednak zmusić go do używania operatorów bool ' A (tj. operatorów OR, AND, etc) 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 wierzę, że znacznie przewyższa wiele innych bibliotek wyszukiwania javascript, które próbowałem, i ma wsparcie bool ' s, filtrowanie wyszukiwania & paginacji.

Możesz wpisać listę z obiektów javascript dla danych wyszukiwania (tj. przechowywania), 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 dla każdego wyszukiwania.

Oto rozwiązanie dostarczone przez @ InternalFX, ale w JS (użyłem go tak dzielą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 coffeescript bigram przez InternalFx i zrobiłem z niego ogólne rozwiązanie n-gram (możesz dostosować rozmiar gramów).

Jest to TypeScript, ale można usunąć adnotacje typu i działa dobrze jako vanilla JavaScript, jak również.

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

Spróbuj w maszynopisie plac zabaw

(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/

Fuzzy Sort jest biblioteką javascript jest pomocny do wykonywania dopasowania łańcuchów z dużej kolekcji danych.

Poniższy kod pomoże użyć sortowania rozmytego w reaccie.js.

1. Install fuzzy sort through npm,

   npm install fuzzysort
   

2. Stwórz zmienną referencyjną,

   const fuzzysort = require('fuzzysort')
   

3. Użyj metody go (), aby znaleźć dopasowane łańcuchy

   search(keyword, category) {  
     return fuzzysort.go(keyword, data[category]);
   }
   

Pełny kod demo w reaccie.js

import React from 'react';
import './App.css';
import data from './testdata';
const fuzzysort = require('fuzzysort');

class App extends React.Component {
  constructor(props){
    super(props)
    this.state = {
      keyword: '',
      results: [],
    }
    console.log("data: ", data["steam_games"]);
  }

  search(keyword, category) {  
    return fuzzysort.go(keyword, data[category]);
  }

  render(){
    return (
      <div className="App">
        <input type="text" onChange={(e)=> this.setState({keyword: e.target.value})}
          value={this.state.keyword}
        />
        <button onClick={()=>this.setState({results: this.search(this.state.keyword, "steam_games")})}>Search</button>
        {this.state.results !== null && this.state.results.length > 0 ?
          <h3>Results:</h3> : null
        }
        <ul>
        {this.state.results.map((item, index) =>{
            return(
              <li key={index}>{item.score} : {item.target}</li>
            )
          })
        }
        </ul>
      </div>
    );
  }
}

export default App;

Po Więcej patrz FuzzySort