Jak wybrać najbardziej prawdopodobną opcję z listy na podstawie wprowadzania tekstu użytkownika

11

Pracuję nad aplikacją OCR, w której muszę wybrać opcję opartą na wprowadzaniu tekstu przez użytkownika.

Ex:
Available Options:
["python", "ruby", "java", "clojure", "haskell"]

Input: kava
Output: java

Input: ruby
Output: ruby

Input: clujuro
Output: clojure

etc.. 

moja aplikacja jest oparta na pythonie, czy istnieje już algorytm do rozwiązania tego problemu.

Shiv Deepak
źródło
1
Może nie warto tego poprawiać teraz, ale IMO bardziej odpowiednim tytułem byłoby „jak określić odległość (różnicę) między strunami”
Jeff Welling
3
@Jeff: i nigdy nie znalazłbym tego pytania, ponieważ nie miałbym pojęcia, że ​​to, czego potrzebuję, można by nazwać „różnicą odległości” ... I to nie jest jedyny powód, aby nie umieszczać rozwiązania, którego potrzebujesz pytanie. Może to uniemożliwiać ludziom sugerowanie alternatywnych rozwiązań aktualnie występującego problemu. Przykład: odpowiedź lektora.
Marjan Venema,
1
Chodzi mi o to, że teraz, kiedy już wiesz, użycie dokładniejszego tytułu może pomóc w uzyskaniu odpowiedzi od osób, które nie wiedzą, co znaczy „jak wybrać najbardziej prawdopodobny ...”, ale kto rozpozna „odległość między łańcuchami”, ale do każdej jego własności. To była tylko sugestia. Nie wiedziałem, co masz na myśli, i prawie nie kliknąłem twojego pytania, ponieważ to wszystko.
Jeff Welling,

Odpowiedzi:

10

Odbywa się to za pomocą algorytmów kategorii „ przybliżone dopasowanie ciągu ”. Częstą miarą do porównywania dwóch łańcuchów jest odległość Levenshteina . Jest to implementacja Pythona dostępny tutaj .

Zasadniczo porównujesz dane wejściowe z możliwymi wyjściami i wybierasz ten o najmniejszej odległości do pożądanego wyniku.

Artykuł w Wikipedii wymienia także różne inne algorytmy, które możesz wypróbować, jeśli potrzebujesz czegoś bardziej szczegółowego.

Sokół
źródło
Miałem podobny problem z rubinem i tak właśnie go rozwiązałem.
Jeff Welling,