31 results about "Levenshtein distance" patented technology

This invention relates to the Pattern Recognition (PR) of noisy / inexact strings and sequences and particularly to syntactic Pattern Recognition. The present invention presents a process by which a user can recognize an unknown sting X, which is an element of a finite, but possibly larger Dictionary, H, by processing the information contained in its noisy / inexact version, Y, where Y is assumed to contain substitution, insertion or deletion errors. The recognized string, which is the best estimate X+ of X, is defined as that element of H which minimizes the Generalized Levenshtein Distance D(X, Y) between X and Y, for all X<H. Rather than evaluate D(X5Y) for every X<H sequentially, the present invention achieves this simultaneously for every X<H by representing the Dictionary as a Trie, and searching the Trie using a new Al-based search strategy.

A computer-implemented method for matching user inputted text to stored text. The user inputted text is compared to each of the text strings stored in a database using a Levenshtein distance algorithm. For each comparison, the Levenshtein distance is analyzed to determine exact matches, non-matches, and probable matches. Probable matches are further analyzed using a keyboard distance algorithm to differentiate between matches and non-matches.

Methods and systems of mapping of an optical character recognition (OCR) text string to a code included in a coding dictionary by supplementing the Levenshtein Distance Algorithm (LDA) with additional information in the form of adjustments based on particular character substitutions, insertions and deletions together with weighting based on multiple alternatives for the OCR text string. In one embodiment, an OCR text string mapping method (100) includes receiving (110) an OCR text string, comparing (120) it with selected text strings from a coding dictionary, computing (130) modified Levenshtein distances associated with the comparisons by determining (140) substitution penalties, determining (150) insertion penalties, determining (160) deletion penalties and combining (170) the penalties, selecting (180) the best matching text string from the coding dictionary based on the modified Levenshtein distances, determining (190) whether a maximum threshold distance is met, and assigning (200) a code associated with the best matching text string to the OCR text string when met, and assigning (210) a null or no code when not met.

A computer-implemented method for matching user inputted text to stored text. The user inputted text is compared to each of the text strings stored in a database using a string similarity score determined using a Levenshtein distance algorithm, the n-gram or trigram methods, the Jaro-Winkler algorithm, the Cosine similarity algorithm, the Hamming distance algorithm, the Damerau-Levenshtein distance algorithm, or similar. For each comparison, the string similarity score is analyzed to determine exact matches, non-matches, and probable matches. Probable matches are further analyzed using a keyboard distance algorithm to differentiate between matches and non-matches.

The present invention provides a question-answer matching method and device, relating to the technical field of intelligent question-answer, including a question-answer matching method, including: extracting keywords in the input question text; Determine the target matching question text in the question bank; based on the Lewenstein distance algorithm, determine the best matching question text with the highest similarity with the input question text from the target matching question text; according to the best matching question text, Output the answer text corresponding to the input question text. The invention can output answers corresponding to the input question sentences in a relatively short time, which can not only shorten the question-answer matching time, but also improve the accuracy rate.

The invention discloses a lip detection and reading method based on cascade feature extraction. The invention first detects the lip area of ​​the input video through the Viola Jones method based on the Haar classifier and the adaptive advancement algorithm; then performs threshold binarization on the detection area according to the color characteristics of the lip area to realize lip area extraction , the image information is concentrated in the corner area of ​​the data matrix through the discrete cosine transform, and the threshold value screening method is used to extract the data; then, the dimensionality extraction of the features with the highest contribution value is performed through the principal component analysis method, so that the data is further reduced in dimension; the sample data is used Establish a sequence dictionary tree for recognition, use Levenstein distance for sequence similarity analysis and fuzzy matching; finally, combine the static features of each frame with the dynamic features of the video, and complete the lip area reading through dynamic sequence query. The invention can improve the speed and accuracy of lip reading through the multi-level extraction and dimension reduction of the image features of the lip area, and has good implementability and robustness.

The invention provides a deep learning evaluation model, an input method pinyin error correction method and device, which uses a method based on an automatic state transition machine to realize efficient levenshtein distance (editing distance) matching between input pinyin strings and standard syllables. Then, through the evaluation model based on deep learning, the combination score of the currently input pinyin string and different approximate standard syllables is given. Finally, by using dynamic programming-based calculations, the optimal combined pinyin analysis results are obtained. The present invention can correct possible wrongly input syllables, output correct and most probable syllable division results, solve possible ambiguity problems, take into account the localized information platform, and improve the operating efficiency of the input method.