Koncepcja wyszukiwania rozmytego bazy danych

13

Zastanawiałem się nad tym i próbowałem znaleźć rozwiązania, w jaki sposób rozmyte wyszukiwanie w bazie danych, jeśli na przykład użytkownik wpisze błąd w pisowni. Masz rażące problemy z logiką? Czy to zadziała i czy zrobiono to wcześniej?

Nasz stół, który chcemy przeszukać:

**tblArticles**
Body - Soundex_Body - CharacterCoded_Body

Tak więc przechowujemy surowy tekst do fizycznego wyświetlenia. Pozostałe 2 kolumny są używane do wyszukiwania, które są wstępnie obliczane w następujący sposób:

Soundex

Ciało jest podzielone na słowa i przetłumaczone na wersję soundex. IE, wynikowe ciało może być coś takiego:

H252 B54 C23 E33... etc

Aby ktoś mógł wpisać „dinosore”, a treść artykułu brzmi „dinozaur”, oba oceniają na B26. Następnie uruchamiamy LIKE na wartości soundex wyszukiwanego hasła.

Kodowanie znaków

Biorąc pod uwagę mapowanie znaków, które odwzorowuje znaki na liczby pierwsze, IE:

h = 2
e = 3
l = 5
o = 7
p = 11
c = 13

help = 2*3*5*11     =   330
hello = 2*3*5*5*7   =   1050
hell = 2*3*5*5      =   150
hlep = 2*5*3*11     =   330
cello = 13*3*5*5*7  =   6825

Jeśli użytkownik chciałby wpisać „cześć”, ale zmienił dwa lub więcej znaków, na przykład „hlelo”, oceniałby na ten sam numer. Podziel surowe ciało na słowa, koduj pierwsze każde słowo i przechowuj w bazie danych, uzyskując pole, które wygląda:

330 6825 330 1050... etc

Możemy następnie polubić tę wartość, aby dopasować błędne typy.

Korzyści

  • Literówki chronione przed
  • Chronione przed błędami pisowni fonetycznej
  • Bardziej przyjazny dla rodzimych użytkowników języka angielskiego
  • Działa w dowolnym języku (w którym działa soundex)

Komentarze i przemyślenia? Rodzaj wyszukiwania wielowarstwowego. Możesz oczywiście zwracać wartości masy, aby było jeszcze lepiej (IE dosłowne dopasowanie tekstu jest warte więcej), ale czy jest to dobre rozwiązanie dla błędów ortograficznych i osób, które nie są rodzimymi użytkownikami języka angielskiego podczas wyszukiwania?

Tomek
źródło
Byłoby ciekawie zobaczyć, jak to się ma do Trigram Search.
Rich
Chciałbym mieć coś takiego dla wordpress ...
Kit Menke
Czy używanie liczb pierwszych do funkcji mieszającej uniemożliwia kolizje słów, które nie zawierają identycznych metod? Wydaje się, że powinno być możliwe utworzenie długiego słowa z dużą ilością liter o niskiej wartości, które mają taką samą wartość jak krótkie słowo z kilkoma literami o dużej wartości, ale nie znam dużej teorii liczb, więc to prawdopodobnie dobrze udowodnione w ten czy inny sposób ...
glenatron
1
@Glen Afaik pomnożenie liczb pierwszych zawsze generuje unikalny numer. Anagramy się jednak zderzą, ale nie wiem, na czym polega problem, po prostu o to chodzi, aby szybko znaleźć anagramy.
Tom
@Glen: Zobacz unikalne twierdzenie faktoryzacji dotyczące wyjątkowości.
Steven Evers

Odpowiedzi:

2

Istnieje wiele innych algorytmów wyszukiwania. Smith-Waterman jest jednym z lepszych tekstów ludzkich, a BLAST jest (jak dotąd) najlepszy do wyszukiwania sekwencji DNA. Gdy zostanie wyświetlony tekst z różnymi błędami ortograficznymi, np. hlepZamiast help, to szukasz minimalnej odległości edycji .

Aby zaimplementować bibliotekę wielu tych funkcji w CLR w SQL Server 2005 (i późniejszych), spójrz na źródłowy projekt kuźni SimMetrics . Wpis na blogu o SimMetrics .
http://staffwww.dcs.shef.ac.uk/people/S.Chapman/simmetrics.html

Soundex został opracowany, ponieważ podstawowe różnice między regionalnymi odmianami mowy występowały prawie wyłącznie w samogłoskach - dlatego odrzuca je. Nie radzi sobie z transponowanymi literami.

Tangurena
źródło
2

Apache Solr obsługuje synonimy i korekty pisowni - choć nadal jest nieco szorstki na brzegach.

Wyszukiwanie rozmyte może być realizowane za pomocą Ngrams,

Porter Stemmer: http://tartarus.org/~martin/PorterStemmer/

oraz baza danych języków, taka jak http://wordnet.princeton.edu/

... ale projekty takie jak Xapian i Solr zajmują się tym w większości.

Jeśli chcesz zbudować własny silnik analizujący / wyszukujący wyszukiwane słowa, sugerowałbym umieszczenie wygenerowanych tokenów lub terminów w istniejącej bazie danych zaprojektowanej do wyszukiwania języka.

Ben DeMott
źródło
1

Jakiś czas temu zrobiłem coś takiego dla adresów, które sprawdzą, ile zmian zajmie transformacja jednego łańcucha na inny, i zwrócę wartość liczbową z zakresu od 0 do 1, aby sprawdzić, jak ściśle oba pasują.

Udało się świetnie, ponieważ zwróciłoby wysoką wartość dla przedmiotów takich jak N / North, St / Street, EastMain / MainEast itp. Pomysł pochodzi z tego linku CodeProject

Rachel
źródło
Czy kod napisany dla adresu pasuje do open source?
Thismatters,
@Thismatters Nie mam dostępu do kodu, ale link w mojej odpowiedzi powinien zawierać logikę. Zasadniczo chcesz tylko zobaczyć, ile zmian zajmie przejście jednego łańcucha na drugi, a im mniej zmian, tym bliżej ich
Rachel
0

Jeśli pasujesz do nazwisk, osób lub miejsc, lista synonimów może działać znacznie lepiej.

Soundex nie będzie pasował do „Dick == Richard”, „Kit == Christopher” lub „Ms. == Mrs.”

Martin Beckett
źródło