Вопросы с тегами [levenshtein-distance]

1

голосов
0

ответ
36

Просмотры

Текст анонимного в контексте Record Linkage

У меня есть два набора данных, что мне нужно, чтобы связать вместе, в том смысле, что я должен найти записи, которые появляются в обоих наборах данных в пределах определенной погрешности (например, первое имя человека является орфографической ошибкой в ​​одном из множеств, человек переехал, женился и, таким образом, получил другую фамилию и т.д.) Поскольку данные чувствителен, он должен быть анонимизированной. Тем не менее, я не могу использовать стандартные методы обезличивания (хэширования, например), так что не будет сохранять некоторые свойства жизненно важное значение для связывания записей. Поэтому я искал способ, чтобы мои анонимные текстовые данные таким образом, что она сохраняет, например, расстояния Левенштейна. Существуют ли такие методы?
konewka
1

голосов
2

ответ
977

Просмотры

питон setup.py установить ошибку [WinError 3] Система не может найти указанный путь

Я пытаюсь установить Python пакет Python-Левенштейн с помощью: питон setup.py установить Но я возвращаю ошибку: ошибка: [WinError 3] Система не может найти указанный путь: «C: \ Program Files (x86) \ Microsoft \ Windows SDKs \ v8.1 \ Lib»Затем я использую пункт установить питон-Левенштейн, но он возвращает то же самое error.I пытается установить другие пакеты питона (т.е. jieba), это работает! Я не знаю, почему я не могу установить питон -Levenshtein. Моя ОС 64-бит, и python3.6 это 32-bit.Is есть какое-то влияние? Может кто-нибудь мне помочь?
qys
1

голосов
1

ответ
1k

Просмотры

Levenshtein implementation with PHP and database

У меня есть форма поиска. Если пользователь делает опечатку как Ager вместо гнева, он должен еще показать соответствующие результаты вместо отображения найдено 0 материалов. Я наткнулся на функции PHP Левенштейна и пример, что они дали с массивом именно то, что я хочу [за исключением того, что пользователь может ввести фразу, а не одно слово], но я хотел бы реализовать его с базой данных, но не имею ни малейшего представления о том, как идти о реализации его с базой данных. Это мой код: если (пусто ($ поиск)!) {Попробуйте {$ запрос = $ это -> _ db-> подготовки ($ SQL); $ Query-> Execute (); если ($ query-> сверку () == 0) {$ foundRows = $ это -> _ db-> запрос ( "SELECT FOUND_ROWS ()") -> fetchColumn (); в то время как ($ строка = $ query-> выборки (ПДО :: FETCH_ASSOC)) {$ cQuote = $ этом-> highlightWords (htmlspecialchars ($ строки [ 'cQuotes']), $ поиска); $ Search_result [] = массив ( 'успех' => верно, 'totalRows' => $ foundRows, 'cQuotes' => $ cQuote, 'vAuthor' => $ этом-> ч ($ строки [ 'vAuthor']), 'vBookName' => $ этом-> ч ($ строки [ 'vBookName']), 'Vref' => $ этом-> ч ($ строки [ 'Vref'])); } $ = Ответ json_encode ($ search_result); эхо $ ответа; вернуть TRUE; } Еще {$ ех = «Ничего не найдено для» $ поиск. $ This-> ErrorMsg ($ ех); } $ Query-> closeCursor (); } Поймать (Exception $ ех) {$ ех = "Проблема:" $ ех;. $ This-> ErrorMsg ($ ех); }} Еще {$ ех = «Пожалуйста, введите что-то» ; $ This-> ErrorMsg ($ ех); } Я хотел бы добавить, что я использую MySQL + PDO.
input
1

голосов
1

ответ
545

Просмотры

Левенштейн для неанглийских языков

Какие другие языки кроме английского делает Левенштейн поддержку ее реализации? Я знаю, что язык должен иметь представление на основе одного символа (а не два или более символов рассматриваются как единое целое, как на голландском языке?), И хотел бы знать, какие язык осени / не попадаю в этой категории. Благодаря Абхишек S
London guy
1

голосов
1

ответ
314

Просмотры

отношение нечеткого Левенштейна питона получило ранний выход?

Я пытаюсь сравнить 100k строк друг друга. Я не могу еще больше уменьшить размер проблемы (т.е. #strings в наборе). Я использую соотношение Левенштейн для сравнения. Если это отношение больше, чем 0,9, я хочу, чтобы хранить 2 строки в списке. Мой вопрос об оптимизации времени выполнения. Так как 0,9 мои критерии, есть способ, чтобы передать это значение Levenshtein.ratio () и ожидать скорый выход в негативных случаях? Если существует способ выйти рано, некоторые выполнения могут быть сохранены. Является ли это возможно в алгоритме Левенштейн, чтобы получить соотношение рано до расчета полного расстояния (ов). Например, импорт Левенштейн Levenshtein.ratio ( «много времени выполнения», «почему бы не ранний выход в этом случае, принимая намеченное соотношение») Есть ли что-то вроде: Levenshtein.ratio ( «много времени выполнения», "почему бы не ранний выход в этом случае, взяв целевое соотношение», 0,9)
syam
1

голосов
1

ответ
431

Просмотры

Deleting a word from a specific implementaion of trie in Python

Я свой рода новым для datastructures и я реализация синтаксического дерева, чтобы неоднозначность базы данных имен с помощью редактирования расстояния. Я использую следующую реализацию: http://stevehanov.ca/blog/index.php?id=114 синтаксического дерева, которая в основном: класс TrieNode: Защита __init не __ (Я): self.word = None self.children = { } глобальный + = 1 Защита вставка (самоощущение, слово) NodeCount NodeCount: узел = сам для буквы в слове: если письмо не в node.children: node.children [письмо] = TrieNode () узел = node.children [письмо] узел .word = слово # считывают файл словаря в Trie Trie = TrieNode () для имени в именах: WordCount + = 1 trie.insert (имя) Это делает работу красиво, как он вставляет все имена в синтаксическое дерево. Теперь я иду по списку имен у меня есть один на один, и использовать синтаксического дерева, чтобы вернуть список всех имен, которые находятся на определенном расстоянии от редактирования переданного имени. Я хочу, чтобы затем удалить все имена из синтаксического дерева, которые были возвращены в списке. Есть ли быстрый способ сделать это? Спасибо!
user1773010
1

голосов
2

ответ
647

Просмотры
1

голосов
2

ответ
189

Просмотры

Comparing items in large list - finding items differing in 1 letter by length - Python

I am looking to solve a problem I've been stuck on in Python. I have a single file, with one column, which contains approx. 6,000 lines. For each line, every item is unique (this file was filtered to remove duplicates froma 40,000 line file). The items in each row vary in length, where some are equal in length to others. An example of a single line: IGHV3-30/33rn-IGHJ4-CARDPSLSSMITFGGVIVTRGYFDYW Or more examples with tab separated after third "-" (differing first parts): IGHV3-23-IGHJ4 CAKDRGYTGYGVYFDYW IGHV4-39-IGHJ4 CARHDILTGYSYYFDYW IGHV3-23-IGHJ3 CAKSGGWYLSDAFDIW IGHV4-39-IGHJ4 CARTGFGELGFDYW IGHV1-2-IGHJ2 CARDSDYDWYFDLW IGHV1-8-IGHJ3 CARGQTYYDILTGPSDAFDIW IGHV4-39-IGHJ5 CARSTGDWFDPW IGHV3-9-IGHJ3 CANVPIYSSSYDAFDIW IGHV3-23-IGHJ4 CAKDWELYYFDYW IGHV3-23-IGHJ4 CAKDRGYTGFGVYFDYW IGHV4-39-IGHJ4 CARHLGYNNSWYPFDYW IGHV1-2-IGHJ4 CAREGYNWNDEGRFDYW IGHV3-23-IGHJ3 CAKSSGWYLSDAFDIW IGHV4-39-IGHJ4 CARYLGYNSNWYPFDYW IGHV3-23-IGHJ6 CAKEGCSSGCPYYYYGMDVW IGHV3-23-IGHJ3 CAKWGPDAFDIW IGHV3-11-IGHJ CATSGGSP IGHV3-11-IGHJ4 CARDGDGYNDYW IGHV1-2-IGHJ4 CARRIGYSSGSEDYW IGHV1-2-IGHJ4 CARDIAVPGHGDYW IGHV6-1-IGHJ4 CASGGAVPGYYFDYW In the first column, there are some items that are different. In the second column every item is the unique. The first column items need to match, and then the second column items need to be sorted by a minimum mismatch of 2. Ideally this would be good to do with Levenshtein module since I can put the max, but I need two strings. Is there a way to use Levenshtein on every item in a single list? What I need to do is open this file (I think sorting it by length first may help, however I'm not sure). After all the items are grouped by length, I need to sort these items into groups that differ by 1 character (the strings before the third "-" need to be identical, where the string after the "-" should differ only by 1 char.) I think the problem I'm having is in regards to generating a proper for loop to iterate over the items length. The code I have thus far: import sys import os import Levenshtein inp = sys.argv[1] # Input file containing single column of items with open(inp, "r") as f1: vj = [line.strip() for line in f1] lengths = [] for k in vj: i = len(k) lengths.append(i) lengths_sort = sorted(lengths, reverse = True) uniq_len = [] for i in lengths_sort: if i not in uniq_len: uniq_len.append(i) print uniq_len #For QC purposes def get_new_list(strings, counts, outlist=[]): for s in strings: if len(s) == counts[0]: outlist.append(s) return outlist new_vj = get_new_list(vj, uniq_len, outlist=[]) print new_vj ham = Levenshtein.hamming(new_vj[0], new_vj[1]) print ham So the output I was looking for is good, but not yet complete: [46, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18] 46 ['IGHV3-30/33rn-IGHJ4-CAKDPSLSSMITFGGVIVTRGYFDYW', 'IGHV3-30/33rn-IGHJ4-CARDPSLSSMITFGGVIVTRGYFDYW'] 1 There are two items of length 46 (coincidentally the strings before the third "-" is the same; great) and they differ by only one character between the two strings. My trouble is, 1. how can I iterate through the numbers in the uniq_len list as unput for matching length in the "strings" list (see function in code). 2. I want to create a new list for each differing length. 3. If there are multiple items in each new list, all items much differ by only 1 character. Note: The "-"'s were creating using UNIX paste -d- command with 3 files containing 1 column each to create this file. Would it be easier to paste these files together with a \t as the delimiter to create 3 columns? So, open the file, strip the lines, and one can then match up the 1st column, 2nd column, and see if the third column differs by one or more characters? All help is appreciated.
st.ph.n
1

голосов
2

ответ
1.1k

Просмотры

Левенштейна на диакритические знаки

В PHP я вычисление расстояния Левенштейн с помощью функции Левенштейн (). Для простых символов он работает, как ожидалось, но для диакритических символов, как в примере эхо Левенштейн ( «а», «а»); она возвращает «2». В этом случае только одна замена должно быть сделано, так что я ожидаю, что это вернуть «1». Я что-то пропустил?
Murval
1

голосов
2

ответ
1.5k

Просмотры

Объяснение нормализованного расстояния редактирования формулы

Основываясь на этой бумаге: IEEE Transactions НА PAITERN анализа: вычисление нормализованного расстояния редактирования и приложения В данной работе Нормированное Редактировать расстояние, как следует: Учитывая две строку X и Y над конечным алфавитом, нормированное редактированием расстоянием между X и Y, D (X , Y) определяется как минимум W (P) / л (Р) ш, здесь Р представляет собой путь для редактирования между Х и Y, W (P) представляет собой сумму весов элементарных операций редактирования Р, и L (P) есть число этих операций (длина P). Могу ли я безопасно перевести алгоритм нормализованного расстояния редактирования объяснен выше, как это: нормированное расстояние редактирования = Левенштейн (1 запрос, запрос 2) / макс (длина (запрос 1), длина (запрос 2))
jxn
1

голосов
1

ответ
297

Просмотры

Можете ли вы вес Levenshtien к передней части строки?

Левенштейн, кажется, очень .. agnostic..in плане того, как она набирает расстояние / подобия в терминах. Например: Olive Garden против Олден Garden = 3, тогда как Olive Garden против Olive Garden Restaurant = 11 В реальном мире (как я это вижу или, по крайней мере, для некоторых приложений) последние должен быть взвешено гораздо большей степень. Есть ли модификация или другое «расстояния» инструмент сравнения, который не пытается объяснить, как много для опечатка и транспозиции, что бы веса второго примера выше из-за огромные # 100% матчей на первую часть фразы?
user3649739
1

голосов
1

ответ
212

Просмотры

Левенштейн расстояния, на котором я забочусь только о словах

Я хочу, чтобы проверить расстояние между двумя строками с точки зрения вставки / удаление / редактирование слов. Это похоже на расстояние Левенштейна, но я все равно только о словах, а не символы. Например: «Кот сидел на коврике» и «Собака осторожно сидел на коврике» будет иметь слово расстояние, равное 3. Я работаю с Rosetta кода C ++ скрипт для Левенштейна, но я не могу видеть, как это сделать Это. # include # include с помощью патезраса; // Вычислить Расстояние Левенштейна // Мартин Ettl, 2012-10-05 size_t uiLevenshteinDistance (Const станд :: строка & s1, Const станд :: строка & s2) {сопзЬ size_t м (s1.size ()); сопзЬ size_t п (s2.size ()); если (м == 0) возвращение п; если (п == 0) возвращение м; size_t * Затраты = новый size_t [п + 1]; для (size_t к = 0; K
Tarrare
1

голосов
2

ответ
143

Просмотры

Записать все оптимальные выравнивания последовательностей при расчете Левенштейн расстояния в Julia

Я работаю на расстояния Левенштейна с Wagner-Fischer алгоритма Джулии. Было бы легко получить оптимальное значение, но немного трудно получить оптимальную последовательность операций, как вставки или удаления, в то время как трассировку с правом нижнем углу матрицы. Я могу записать информацию указателя каждого г [я] [J], но это может дать мне 3 направления, чтобы вернуться к д [я-1] [J-1] для подстановки, [я-1] d [J] для удаления и D [I] [J-1] для вставки. Так что я пытаюсь получить все комбинации наборов операций, которые дали мне оптимальное расстояние Левенштейн. Кажется, что я могу хранить одну операции, установленную в одном массиве, но я не знаю, общее количество всех комбинаций, а также там длину, так что это будет трудно для меня, чтобы определить массив для хранения операции, установленной во время подсчета процесс. Как я могу генерировать массивы в то время как сохранить прежние из них? Или я должен использовать Dataframe?
Catcoin7
1

голосов
1

ответ
227

Просмотры

как сделать функцию строки словаря в Lua?

Есть ли способ, если строка близка к строке в таблице будет заменить его на один в таблице? Как и функция проверки правописания, которая ищет через стол и, если вход близок к единице в таблице будет это исправить, так что один в таблице и строка такой же?
joshua chris
1

голосов
1

ответ
373

Просмотры

MySQL ngrams пример индексации

Как я прочитал во многих частях, Ngram индексация может улучшить поиск слов. В этом старом поста он говорит, что он может быть адаптирован для MySQL, но это не говорит о том, как: Левенштейне альтернатива Можно ли поставить некоторый пример, как вы можете использовать эту технику в MySQL? Можно использовать эту технику, чтобы улучшить производительность функции Левенштейна для MySQL ?. Моя потребность найти приближенный текст (как Левенштейн) В ми тестах я использовал Левенштейн () и levenshtein_ratio () функция из: http://www.artfulsoftware.com/infotree/qrytip.php?id=552 SELECT *, levenshtein_ratio ( 'stacoverflou', words_column) как отношение ОТ my_table ORDER BY DESC отношения, которые улучшают производительность (не опечатка, предполагающей первую букву) SELECT *, levenshtein_ratio ( 'stacoverflou', words_column) как отношение ОТ my_table ГДЕ words_column LIKE '% s'
MTK
1

голосов
1

ответ
111

Просмотры

проблема производительности, расстояние редактирования для больших строк LCP против Левенштейнов против SIFT

Так что я пытаюсь вычислить расстояние между двумя большими строками (около 20-100). Препятствием является производительность, мне нужно запустить 20k расстояния сравнения. (Это занять несколько часов) После исследования, я пришел крест несколько алгоритмов, и у меня возникают проблемы, чтобы решить, какой выбрать. (На основе производительности VS точности) https://github.com/tdebatty/java-string-similarity - список характеристик для каждого из алгоритмов. ** EDITED ** Является ли алгоритм SIFT4 хорошо проверенное / relayable? Является ли SIFT4 является правильным алгоритмом для выполнения этой задачи? Как же это так намного быстрее, чем ЖКП на основе / Левинштейн algorithem? Доза SIFT также используется в обработке изображений? или это разные вещи? ответил АМГ Спасибо.
Adi Darachi
1

голосов
1

ответ
58

Просмотры

Левенштейна расстояние редактирования с сепаратором для блоков мульти-символов

Я искал через функцию R adist, agrep, матч, и stringdist, но не нашел способ вычисления расстояния редактирования с сепаратором. Существующие расстояния редактирования: «что» & «жир» = 2 т.е. adist ( «что», «жир») Желаемая функция будет использовать разделитель для обозначения единиц из нескольких символов: «th.at» & «жира» = 1
kneergaard
1

голосов
1

ответ
33

Просмотры

Настройка значений символов питона-Левенштейн

Я использую модуль питона-Левенштейн для анализа ирландского текста языка за большой период времени; в течение долгого времени существует целый ряд орфографических изменений в текст, например, Б.И. -> Б.И. -> BHI, диакритическим над «B» и «ч» после б оба представляют собой ту же грамматическую форму лениция (который не показан в первом период). Между всеми этими формами я хотел бы довольно низкое расстояние, но используя расстояние питон-Левенштейна, как это дает такое же расстояние между Levenshtein.ratio (u'ḃí», u'bí„) = 0,5 и Levenshtein.ratio (U“ Ксите «u'bí») = 0.5, очевидно, незначительные орфографические изменения символа „B“, и это прямое замещение „х“ (иностранное заимствованием для загрузки) не должен иметь один и тот же счет. Так есть ли способ изменить значение удельной characacter изменения, например, уменьшить расстояние Б.И. Б.И., но до расстояния между bị и ХI? Или мне нужно будет производить свою собственную реализацию?
1

голосов
1

ответ
0

Просмотры

Поиск Mysql Полный текст, режим естественного языка: заказ на «близость»

Я использую для полнотекстового поиска функции MYSQL (в Mysql 5.6.33). Если я спичка в режиме естественного языка для почтового индекса, с односимвольной опечаткой, я получить некоторые достойные результаты обратно, в том числе результатов с «правильным» почтовым индексом, но они не в верхнем. Например, есть 10 школ с почтовым индексом «BN2 1TL». Я намеренно орфографические ошибки это как "BN2 1TM" и сделать поиск следующим образом: SELECT record_id, address_string, MATCH (address_string) ПРОТИВ ( "BN2 1TM" на естественном языке РЕЖИМЕ) AS оценка от школы, где MATCH (address_string) ПРОТИВ ( "BN2 1TM "на естественном языке РЕЖИМ)> 0 ORDER BY DESC оценки; При ближайшем рассмотрении, это потому, что поиск выкупил все результаты, которые имеют либо «BN2» или «1TM» в своей колонке address_string, и все они имеют точно такой же счет, и поэтому в произвольном порядке, эффективно. , Это вполне разумное поведение, но было бы здорово, если бы я мог получить счет, чтобы принять «близость» во внимание, что означает, что для поиска на «BN2 1TM», «BN2 1TL» будет забито более высоко, чем «BN2 3PQ ». Есть ли способ сделать это? EDIT: Я вспомнил, что этот вид близости технически называется «Левенштейна», который является ссылкой на алгоритм Левенштейна для определения, сколько замены необходимы, чтобы превратить одну строку в другую. Таким образом, я предполагаю, что мой вопрос может быть как «Могу ли я получить MYSQL FULLTEXT естественного языка РЕЖИМ скоринг принять Левенштейн во внимание»? Это вполне разумное поведение, но было бы здорово, если бы я мог получить счет, чтобы принять «близость» во внимание, что означает, что для поиска на «BN2 1TM», «BN2 1TL» будет забито более высоко, чем «BN2 3PQ ». Есть ли способ сделать это? EDIT: Я вспомнил, что этот вид близости технически называется «Левенштейна», который является ссылкой на алгоритм Левенштейна для определения, сколько замены необходимы, чтобы превратить одну строку в другую. Таким образом, я предполагаю, что мой вопрос может быть как «Могу ли я получить MYSQL FULLTEXT естественного языка РЕЖИМ скоринг принять Левенштейн во внимание»? Это вполне разумное поведение, но было бы здорово, если бы я мог получить счет, чтобы принять «близость» во внимание, что означает, что для поиска на «BN2 1TM», «BN2 1TL» будет забито более высоко, чем «BN2 3PQ ». Есть ли способ сделать это? EDIT: Я вспомнил, что этот вид близости технически называется «Левенштейна», который является ссылкой на алгоритм Левенштейна для определения, сколько замены необходимы, чтобы превратить одну строку в другую. Таким образом, я предполагаю, что мой вопрос может быть как «Могу ли я получить MYSQL FULLTEXT естественного языка РЕЖИМ скоринг принять Левенштейн во внимание»? будет забито более высоко, чем «BN2 3PQ». Есть ли способ сделать это? EDIT: Я вспомнил, что этот вид близости технически называется «Левенштейна», который является ссылкой на алгоритм Левенштейна для определения, сколько замены необходимы, чтобы превратить одну строку в другую. Таким образом, я предполагаю, что мой вопрос может быть как «Могу ли я получить MYSQL FULLTEXT естественного языка РЕЖИМ скоринг принять Левенштейн во внимание»? будет забито более высоко, чем «BN2 3PQ». Есть ли способ сделать это? EDIT: Я вспомнил, что этот вид близости технически называется «Левенштейна», который является ссылкой на алгоритм Левенштейна для определения, сколько замены необходимы, чтобы превратить одну строку в другую. Таким образом, я предполагаю, что мой вопрос может быть как «Могу ли я получить MYSQL FULLTEXT естественного языка РЕЖИМ скоринг принять Левенштейн во внимание»?
Max Williams
1

голосов
2

ответ
208

Просмотры

Левенштейн Транспонирование Расстояние

Как я могу реализовать транспонирования / обмен / вертеть / обмен расстояния в одиночку с помощью динамического программирования. Я должен подчеркнуть, что я не хочу, чтобы проверить для других операций (т.е. копирование, удаление, вставка, убивать и т.д.) просто транспонировать / своп. Я хотел бы применить алгоритм Левенштейна просто для подкачки расстояния. Как бы код выглядеть?
Vlad Otrocol
1

голосов
1

ответ
0

Просмотры

Изменение нахождения расстояния редактирования только вставок и удалений?

Мне нужно найти расстояние редактирования между словом и его отсортированным словом (например: яблоко и aelpp), используя только вставку и удаление рекурсивно. Я нашел несколько источников, которые используются вставки, делеции и замены, но я не знаю, как использовать только вставки и удаления. Это код, который я нашел: Защиту л.д. (s, т): если не s: вернуть LEN (т), если не т: возвращает Len (ы), если S [0] == т [0]: возвращение LD (s [ 1:], т [1:]) l1 = LD (s, T [1:]) 2 = LD (с [1:], т) l3 = LD (с [1:], т [1:]) вернуться 1 + мин (l1, l2, l3) Какие редактирует должны были бы быть сделано, чтобы найти только количество вставок и удалений?
Altaaf Ackbar
1

голосов
3

ответ
574

Просмотры

Как оптимизировать этот расчет расстояния Левенштейна

Таблица А имеет около 8000 строк, и в таблице B имеет около 250 000 строк. Без функции Левенштейн запрос занимает менее 2 секунд. С помощью функции включены она занимает около 25 минут. SELECT * FROM библиотеки а, классификации В, где a.`release_year` = b.`year` И a.`id` является недействительным и levenshtein_ratio (a.title, b.title)> 82
garethdn
1

голосов
4

ответ
587

Просмотры

Строка ключ Фразовое

В Левенштеину, как ты, Hw ру, то как U, и вы ар HW можно сравнить, как же, есть в любом случае я могу достичь этого, если у меня есть такая фраза как. фраза привет, меня зовут Джон лани. Я живу в Нью-Йорке. Как тебя зовут? Фраза Меня зовут Брюс. WHT ваше имя ключевая фраза Каков ваш ответ имя мое имя денщика. им получать входные данные от user.I есть таблица со списком возможных запроса с ответом. например, пользователь запросит о «его имени», есть ли способ я могу проверить, имеет ли предложение ключевую фразу, как Что такое ваше имя и, если его нашли это будет возвращать возможный ответ, как фраза = 'привет, меня зовут Джон Доу. Я живу в Нью-Йорке. Как тебя зовут?' // Я знаю, что один будет работать, если {возвращение $ ответ (StrPos ($ фраза «Что такое ваше имя») == ложь!); } // но что если пользователь неправильно напечатает, если (StrPos ($ фразы, «WHT тебя зовут») == лжи!) {Возвращение $ ответа; } Есть я путь для достижения этой цели. Левенштейн отлично работает, только если длина строк не так давно с сравниваемой строкой. как привет, WHT ваше имя мое имя денщика. но если это так долго привет, меня зовут Джон лани. Я живу в Нью-Йорке. Как тебя зовут? ее не работает хорошо. если короче фраза, она будет идентифицировать короткую фразу, которые имеют более короткое расстояние и возвращает неправильный ответ я думал другой путь вокруг, чтобы проверить некоторые ключевые фразы. так что любая идея, чтобы достичь это? я работал на что-то вроде этого, но, может быть, есть лучший и правильный способ я думаю, что $ samplePhrase = «привет, И. М. Spongebob, я работаю в Krabby пирожка. я люблю пирожки. Whts ваше имя моего друга '; $ = Ключевая фраза " Как тебя зовут'; получить первый символ ключевой фразы. Это было бы 'W' перебирать $ символов samplePhrase и сравните первый символ ключевой фразы H, I,, I, M,, s, p и т.д.. , если keyPhrase.char = samplePhrase.currentChar прибудет keyPhrase.length прибудет samplePhrase.currentChar индекса получить подстроку samplePhrase базы по индексу currentChar к keyPhrase.length первого он получит будет работать на Krabby ра сравнить работу в Krabby годовых до $ ключевой фразы ( «Как твое имя»), используя levenstiens расстояние и проверить его лучше использовать semilar_text. 11.if не равны, а расстояние до большого процесса повторения. currentChar прибудет keyPhrase.length прибудет samplePhrase.currentChar индекса получить подстроку samplePhrase базы по индексу currentChar к keyPhrase.length первого он получит будет работать на Krabby ра сравнить работу в Krabby годовых до $ (ключевой фразы «Как тебя зовут») используя levenstiens расстояние и проверить его лучше использовать semilar_text. 11.if не равны, а расстояние до большого процесса повторения. currentChar прибудет keyPhrase.length прибудет samplePhrase.currentChar индекса получить подстроку samplePhrase базы по индексу currentChar к keyPhrase.length первого он получит будет работать на Krabby ра сравнить работу в Krabby годовых до $ (ключевой фразы «Как тебя зовут») используя levenstiens расстояние и проверить его лучше использовать semilar_text. 11.if не равны, а расстояние до большого процесса повторения.
Snippet
1

голосов
1

ответ
402

Просмотры

Расстояние Левенштейна зацикливание в Python

У меня есть набор эталонных слов (пишется правильно), и мне нужно принять пользовательского ввода слова. Входное слово сравнивается с эталонным списком с использованием расстояния Левенштейна и мне нужно, чтобы вернуть слово из списка ссылок, который имеет самую низкую стоимость. Кроме того, эта ссылка список отсортирован по частотам так, более высокие частоты появляются в верхней части. В случае, если расстояние равно 2 слов, слово возвращается с более высокой частотой. «NWORDS» мой список ссылок, отсортированный по частоте. «Кандидат» является пользовательский ввод слова. Код: для слова в NWORDS: #iterate над всеми словами в иом я = jf.levenshtein_distance (кандидат, слово) #compute расстояния для каждого слова с пользовательским вводом #dont знать, что делать здесь возвращать слово #FUNCTION возвращает слово из списка рефов с самое низкое расстояние и высокая частота встречаемости.
Hypothetical Ninja
1

голосов
2

ответ
403

Просмотры

Оптимизировать скорость расстояния Левенштейна многих слов

У меня есть словарь массива ячеек, который содержит много слов (приблизительно 15 000). Я хочу, чтобы вычислить функцию strdist (для вычисления расстояния Левенштейна) для всех пар слов. Я попытался двумя способами, но они оба очень медленно. Что может быть более эффективным решением? Вот мой код (dict_keys мой элемента массив длина т):) матрица 1 = разреженные (м, м); при г = 1: м-1; матрица (я, :) = cellfun (@ (и) strdist (dict_keys {я}, и), dict_keys); Конец 2) матрица = разреженные (м, м); при г = 1: м-1; при = + 1: т матрица (I, J) = strdist (dict_keys {I}, {dict_keys J}); конец конец
charles
1

голосов
1

ответ
307

Просмотры

Revise existing Levenshtein distance code to accommodate different operation costs

I have found a lot of sources that determine Levenshtein distances (LD) between two strings. However all of them assume the costs for substitution, insertion, and deletion operations are all set to 1. This source for C++ is very efficient, which I am trying to adapt below to allow different costs per operation. #include #include #include size_t levenshtein_distance(const std::string &a, const std::string &b); int main() { std::string a, b; a = "roger"; b = "Roger"; std::cout
Buddy
1

голосов
1

ответ
2.1k

Просмотры

расчет коэффициента питона-Левенштейна

У меня есть следующие две строки: A = «Bjork Гудмундсдотир» Ь = «Ь. Gudmundsson Гуннар»The Левенштейн расстояние между ними равно 12. Когда я использую следующую формулу для расстояния Левенштейн, я получаю несоответствие 0,01 с библиотекой Python-Левенштейн: >>> Ldist / макс (LEN (а), (б Len )) >>> поплавок (12) / 21 0,5714285714285714 # питона-Левенштейна Levenshtein.ratio (а, б) 0,5853658536585366 # difflib >>> сл = difflib.SequenceMatcher (а = а, Ь = Ь) >>> seq.ratio () +0,5853658536585366 Чем объясняется эта разница? Что я неправильно делаю в моем расчете. Обратите внимание, что я проверил это как питон-Levenshtein.ratio вычисляется подобный вопрос, и это не совсем ответ, что я прошу. Может кто-то пожалуйста, объясните формулу, которая используется для расчета выше соотношения?
David542
1

голосов
1

ответ
68

Просмотры

IS это быстрее, чтобы использовать Левенштеин при запросе строк или на PHP?

В настоящее время я использую следующий запрос: (я использую следующий implmenetation Левенштейна () ВЫБОР название FROM db_full WHERE MATCH ( `title`) ПРОТИВ («Гарри Поттер и Дары Смерти»В BOOLEAN MODE) и Левенштейна (» Гарри Поттер и Дары смерти, `title`) между 0 и 15 мне было интересно, если это было быстрее использовать комбинацию MySQL + PHP что-то вроде ниже $ testQ =«SELECT название FROM db_full WHERE MATCH ( `title`) ПРОТИВ ( 'Гарри Поттер и Дары смерти' IN BOOLEAN MODE) ";} результат = $ conn-> запрос ($ testQ), в то время ($ строка = $ result-> FETCH_ASSOC ()) {$ = расстояние Левенштейна ($ v, $ строки [ «название»]); // используя при condinational на расстояние} Какая процедура будет более быстрым и эффективным?
0

голосов
0

ответ
3

Просмотры

Расстояние Левенштейна в узле-sqite3

Какой SQL-запрос позволит мне определить, как выбрать несколько строк на основе расстояния Левенштейн? Например, если (расстояние между словами из разных строк> 3) Дайте мне четыре строки слова Else Попробуйте еще раз
Dark Lotus
1

голосов
1

ответ
218

Просмотры

как PREG соответствовать строке с Левенштейна в PHP

Как я могу PREG соответствовать строке, но терпеть переменное расстояние levensthein в шаблоне? $ Строка = «я есть яблоки и апельсины в течение всего дня»; $ Найти = 'и Orangis'; $ Расстояние = 1; $ матчи = pregMatch_withLevensthein ($ найти, $ расстояние, $ строка); Это вернет «и апельсины»;
Caleb Pitman
1

голосов
1

ответ
134

Просмотры

crate.io полнотекстового поиска размытость

Я хотел бы использовать Левенштейн и Im ищут некоторые примеры. Я уже прочитал документацию, но я не знаю, как это осуществить. Я пытался построить свой собственный анализатор, но он разбился каждый раз, когда я использовал его. Вот документация I follwed: https://crate.io/docs/reference/sql/fulltext.html Пример таблицы:. CREATE TABLE IF NOT EXISTS "тест" "счета" ( "customer_name" STRING INDEX ИСПОЛЬЗОВАНИЕ ПолнТекст С (анализатор = 'стандарт'), "customer_no" STRING, первичный ключ ( "customer_no")) INSERT INTO "тест" "счета" (CUSTOMER_NAME, customer_no) ЗНАЧЕНИЯ ( 'Walmart', 'C00001'). Моя цель будет искать Walmart и вернуть Walmart.
Wk Ali
1

голосов
2

ответ
228

Просмотры

Запись связи с использованием схожести строк Techniques

Мы работаем над проектом рычажного Record. Мы наблюдаем странное поведение со всех стандартной методикой, как Яро Winkler, Левенштейн, N-Gram, Damerau-Левенштейн, индекс Жаккара, Соренсен-Dice Say, String 1 = МИНИ СТАНОК KIT Строка 2 = Weiler 13001 Kit Mini Grinder аксессуары, Для использования с небольшими Угловая шлифмашины Строка 3 = Milwaukee Видео Borescope Вращающийся Inspection Scope, Серия: M-SPECTOR 360, 2,7 в 640 х 480 пикселей с высоким разрешением LCD, пластик, черный / красный в приведенном выше случае строка 1 и строка 2 связаны счет всех методов, как показано ниже. Яро Winkler -> 0,391666651 Левенштейна -> 75 N-Gram, -> 0,9375 Damerau -> 75 Индекс Jaccard -> 0 Соренсен-Dice -> 0 косинус -> 0 Но строка 1 и строка 3 вовсе не связаны между собой, но метод расстояние дают очень высокий балл. Яро Winkler -> 0.
Nischay
1

голосов
1

ответ
91

Просмотры

Левенштейн / изменить расстояние для произвольных последовательностей [дубликат]

Этот вопрос уже есть ответ здесь: Левенштейн типа алгоритм с числовыми векторами 1 ответ Я хочу, чтобы вычислить расстояние Левенштейн между двумя произвольными последовательностями.
cno
1

голосов
1

ответ
730

Просмотры

Firebase advanced fuzzy search with levenshtein ordering and word by word

Search is one of the most important parts of my current application. It needs to feel like a fast, accurate, global search. The app is based on Firebase and I find Firebase's equalTo() / startAt() combination to be fairly lacking in this aspect. What I want to achieve: The results ordered by relevance To match word by word (so öö pime should yield above result) Search in multiple properties (so põhjala pime should yield above result) Fuzzy search (levenshtein?) - pojala should match Põhjala What I already did Instead of using equalTo(), I download an entire branch (for example beers), and loop through it, performing my own contains(). This works and is reasonably fast. However, it lacks all the things I mentioned. Here's the current code. final ArrayList searchResults = new ArrayList(); FirebaseUtil.getBeersRef().orderByChild("name").addValueEventListener(new ValueEventListener() { @Override public void onDataChange(final DataSnapshot ogDS) { int childCounter = 0; for (DataSnapshot ds: ogDS.getChildren()){ childCounter++; if (resultCounter[0] < 5) { final Beer beer = ds.getValue(Beer.class); final String beerId = ds.getKey(); // Limit to five results and remove listener final int finalChildCounter = childCounter; FirebaseUtil.getBreweriesRef().child(beer.getBreweryId()).addListenerForSingleValueEvent(new ValueEventListener() { @Override public void onDataChange(DataSnapshot dataSnapshot) { Brewery brewery = dataSnapshot.getValue(Brewery.class); if (beer.getFullName().toLowerCase().contains(query.toLowerCase()) || brewery.getName().toLowerCase().contains(query.toLowerCase())) { resultCounter[0] = resultCounter[0] + 1; if (resultCounter[0] < 5) { searchResults.add(new SearchBeerAdapter.BeerBrewery(beer, brewery, beerId)); } } // Initialize the adapter once we've hit the end of our results if (finalChildCounter == ogDS.getChildrenCount()){ SearchBeerAdapter sa = new SearchBeerAdapter(searchResults,glide); rv.setAdapter(sa); } } @Override public void onCancelled(DatabaseError databaseError) { } }); } } } @Override public void onCancelled(DatabaseError databaseError) { } }); I'm guessing what needs to be done is each match needs to get a score in searchResults and after we're done looping the ArrayList needs to be sorted by this score. My main question would boil down to how to get the best score considering above criteria. Any libraries or code samples would be extremely welcome. Thanks in advance.
Vic V
1

голосов
1

ответ
79

Просмотры

Соответствующие две строки, позволяющие один своп

Я бегу нечеткий алгоритм соответствия, что позволяет двум струнам иметь одну разницу по метрикам Левенштейн. Но часто возникает опечатка, когда две последовательных буквы перепутаны: Джонатан -> Joanthan профессионально -> profesisonal но эти отличия дают 2 по Левенштейн. Как соответствовать этим отличиям также?
Denis Kulagin
1

голосов
2

ответ
26

Просмотры

как избежать элемент в массиве повторяется в другом кластере?

У меня есть массив или объекты, приблизительно в 58000 уникальных строк (partName). частей = [{_id: 59a942a8c0b7467bf08711df, partName: '0'}, {_id: 59a94299c0b7467bf084a917, partName: '9129'}, {_id: 59a94299c0b7467bf084a918, partName: '9130'}, .., ..] Вот код. То, что я пытаюсь создать кластеры подобных строк. Код делает это, но partName, что уже связан с кластером может снова появляется в другом кластере. Я хочу, чтобы избежать этого. Одно уникальное имя части должно быть подключено только к одному кластеру. Вот пример, который я получаю: { "9129": [ "9132", "9190", "9279"]}, { "9130": [ "9132", "9180", "9190", "9430"] Как вы можете увидеть строки 9132, 9190 повторяются в следующем кластере. Так что мой вопрос: Как удалить строки 9132, 9190 и 9279 после того, как они были связаны с кластером 9129? Функция createCluster (arrayOfParts) {пусть clusterArray = []; для (вар я = 0; г <5; я ++) {пусть кластер = []; у = 1; console.log (arrayOfParts [I]); для (вар J = у; J <arrayOfParts.length; j ++) {если (fuzzball.token_sort_ratio (arrayOfParts [я] .partName, arrayOfParts [J] .partName)> "70") {если (arrayOfParts [I] .partName ! .toLowerCase () == arrayOfParts [J] .partName.toLowerCase () && cluster.includes (arrayOfParts [J] .partName)) {cluster.push (arrayOfParts [J] .partName!); }}} Пусть OBJ = {}; OBJ [arrayOfParts [I]. partName] = cluster.sort (); clusterArray.push (OBJ); } Console.log ( "clusterArray", JSON.stringify (clusterArray, нуль, 2)); console.log ( "clusterArray.length", clusterArray.length); }
Isak La Fleur
1

голосов
1

ответ
204

Просмотры

Проверьте, если одна строка содержит подстроку с расстояния Левенштейна 1 из другой строки

Моя проблема заключается в том, что мы хотим, чтобы наши пользователи, чтобы ввести код, как это: 639195-EM-66-XA-53-WX где-то на входе, так что результат может выглядеть следующим образом: Код 639195-EM-66-XA- 53-WX, позволь мне. Мы все еще хотим соответствовать строке, если они делают небольшую ошибку в коде (Левенштейн 1). Например, код 739195-ЭМ-66-XA-53-WX, впустить меня. (Изменился от 6 до 7, в первой букве коды) Алгоритм должен соответствовать, даже если пользователю перескакивает тир, и это следует игнорировать в нижнем регистре / заглавные буквы. Эти требования легко выполнить, так как я могу удалить все тир и сделать to_uppercase. Есть ли алгоритм для чего-то подобного? Генерирование всех строк с расстоянием 1 из оригинального кода вычислительно дорого. Я также думал об использовании нечто вроде расстояния Левенштейна, но игнорируя отсутствующие буквы, добавленные пользователем во второй строке, но это позволило бы неправильные буквы в середине кода. Поиск кода в пользовательском вводе, кажется, немного лучше, но все еще не очень чистые.
tkowal
1

голосов
1

ответ
1.2k

Просмотры

Pyspark Левенштейн Регистрация ошибки

Я хочу, чтобы выполнить объединение на основе расстояния Левенштейна. У меня есть 2 таблицы: Данные: Что является CSV в HDFS хранилище файлов. один из столбцов является описание болезни, 15K строк. df7_ct_map: стол я вызываю из улья. один из столбцов является заболеванием Индикация, 20K строк. Я пытаюсь соединить обе таблицы путем сопоставления каждого описания с указанием (они представляют собой текстовые описания болезней). В идеале они должны быть одинаковыми, но если оба текста имеют разные Я хочу, чтобы выбрать соответствующий текст, содержащий максимальное количество общих слов. от pyspark.sql.functions импорта Левенштейна joinedDF = df7_ct_map.join (Данные, Левенштейна (df7_ct_map ( "Описание"), данные ( "Индикация")) <3) joinedDF.show (10) Проблема заключается в том данных является DataFrame который почему я получаю следующее сообщение об ошибке: TypeError: «DataFrame» объект не вызываемая TypeError Traceback (самый последний вызов последнего) в двигателе ----> 1 joinedDF = df7_ct_map.join (Данные, Левенштейн (df7_ct_map ( "Описание"), данные ( "Индикация")) <3) Ошибка тип: ' объект DataFrame»не отзывной Некоторые советы? Могу ли я использовать пакет Fuzzywuzzy? Если да, то как?
Lizou
1

голосов
1

ответ
34

Просмотры

Высшее weightage к Prefix

Есть ли способ или метод расстояния, чтобы назначить более высокую Weightage для префикса при расчете подобия? Я знаю метод Яро-Винклер, но его применение ограничено символами. Я ищу сходство слов.
john
1

голосов
3

ответ
1.4k

Просмотры

Могу ли я использовать ActiveRecord, чтобы найти строки на основе ближайшего матча (расстояние Левенштейна)

У меня есть таблица строк в моей базе данных. Я выбираю один из них, А. Как я могу найти остальную часть таблицы, чтобы найти строку наиболее похожей на?
astropanic

Просмотр дополнительных вопросов