Описание тега edit-distance
Строковый показатель, описывающий различия между двумя строками. В частности, это количество операций, которые преобразуют одну строку в другую. Операции включают вставку, удаление, замену или транспонирование символа в строке. Операции можно рассматривать в комбинации и могут иметь разную стоимость.
1
ответ
Создание большого числа случайных последовательностей с минимальным эффективным временем редактирования расстояния
Мне нужно создать программу / скрипт для создания большого количества случайных последовательностей (20 буквенных последовательностей на основе 4 разных букв) с минимальным расстоянием редактирования между всеми последовательностями. "Высокий" - это…
15 сен '17 в 09:00
1
ответ
Отдельный подсчет количества удалений в алгоритме расстояния Левенштейна
Итак, я знаю, что алгоритм расстояния Левенштейна учитывает минимальное количество удалений, вставок и замен, необходимых для изменения строки A в строку B. Но мне было интересно, как можно отдельно отслеживать количество удалений в общем количестве…
10 окт '14 в 08:20
1
ответ
Редактировать матрицу расстояний
Я пытаюсь построить программу, которая принимает две строки и заполняет матрицу расстояния редактирования для них. Меня сбивает с толку то, что для второго строкового ввода он пропускает второй вход. Я попытался очистить буфер с помощью getch(), но …
04 ноя '16 в 00:41
1
ответ
Вычисление расстояния редактирования между значениями столбца данных в панде и заданной строкой
У меня есть один столбец в кадре данных Pandas (на самом деле он довольно большой, около 1,5 миллионов строк текстовых данных), который я хочу сравнить с одной строкой. Для простой проверки / проверки работоспособности я хотел попробовать это только…
20 дек '18 в 20:39
2
ответа
Алгоритм редактирования расстояния Левенштейна, который поддерживает транспонирование двух соседних букв в C#
Я ищу алгоритм для вычисления расстояния редактирования Левенштейна, который также поддерживает случай, в котором транспонируются две соседние буквы, который реализован в C#. например, слова "животные" и "животные": переключение между буквами "n" и …
16 апр '12 в 16:31
1
ответ
Получение ошибки сегментации на многомерном массиве при расчете расстояния Левенштейна
Я пытался вычислить расстояние Левенштейна. Следующий код работает для небольших струн, например, комплект / посадка или сидя / вязание. Но это дало мне ошибку сегментации для строк воскресенье / суббота. После использования GDB(впервые) я понял, чт…
26 фев '12 в 08:19
5
ответов
Как определить различия в двух списках данных
Это упражнение для парней из CS, чтобы осветить теорию. Представьте, что у вас есть 2 контейнера с элементами. Папки, URL-адреса, файлы, строки, это действительно не имеет значения. Что такое алгоритм AN для подсчета добавленного и удаленного? Приме…
24 сен '08 в 13:34
1
ответ
Как мне сбалансировать BK-дерево и нужно ли это?
Я пытаюсь использовать алгоритм Edit Distance для реализации нечеткого поиска в базе данных имен. Я нашел структуру данных, которая предположительно поможет ускорить это с помощью подхода "разделяй и властвуй" - деревья Беркхарда-Келлера. Проблема в…
31 дек '12 в 11:10
5
ответов
Как рассчитать "разницу" между двумя последовательностями точек?
У меня есть две последовательности длиной n и m. Каждый из них представляет собой последовательность точек вида (x,y) и представляет кривые на изображении. Мне нужно выяснить, насколько разные (или похожие) эти последовательности дают тот факт, что …
20 июн '11 в 21:55
1
ответ
Кластеризация строковых данных с помощью ELKI
Мне нужно сгруппировать большое количество строк, используя ELKI на основе расстояния Edit / Levenshtein Distance. Поскольку набор данных слишком велик, я бы хотел избегать предварительно рассчитанных матриц расстояний на основе файлов. Как я могу (…
18 мар '13 в 18:20
10
ответов
Выясните, является ли название компании очень похожим на другое - Python
Я работаю с большой базой данных предприятий. Я хотел бы иметь возможность сравнить два названия компаний по сходству, чтобы увидеть, могут ли они быть дубликатами. Ниже приведен список фирменных наименований, которые должны проверяться как имеющие …
19 июн '11 в 03:52
1
ответ
Преобразовать один список объектов в другой список
Это вопрос теории, поэтому я собираюсь использовать псевдокод. У меня есть список объектов, которые мне нужно преобразовать в другой список. Я реализовал алгоритм Левенштейна, и он отлично работает, но мне нужно сохранить объекты, а не создавать нов…
17 авг '12 в 17:01
2
ответа
Определение последовательности правок, которая дает расстояние Левенштейна
Я делаю некоторую работу, используя расстояние Левенштейна (редактирование), используя динамическое программирование. Я думаю, что понимаю алгоритм Вагнера-Фишера, чтобы сделать это эффективно. Тем не менее, не похоже, что алгоритм является конструк…
10 авг '14 в 19:12
4
ответа
Взвешенное расстояние редактирования неупорядоченной строки
Мне нужен эффективный способ расчета минимального расстояния редактирования между двумя неупорядоченными наборами символов. Как и на расстоянии Левенштейна, которое работает только для последовательностей, мне требуются вставки, удаления и замены с …
12 мар '14 в 09:08
2
ответа
Ищу похожие слова
Я пытаюсь написать модуль проверки орфографии. Он загружает текст, создает словарь из 16-мегабайтного файла и затем проверяет, является ли найденное слово похожим на слово в словаре (схожий = изменяется до двух символов), если это так, то он меняет …
08 апр '12 в 19:30
3
ответа
Псевдокод для скрипта для проверки точности транскрипции / редактирования расстояний
Мне нужно написать скрипт, вероятно, на Ruby, который будет брать один блок текста и сравнивать количество транскрипций записей этого текста с оригиналом, чтобы проверить точность. Если это просто сбивает с толку, я постараюсь объяснить по-другому..…
14 окт '11 в 08:35
2
ответа
Ведение заголовков на расстоянии редактирования
Я бегу редактировать расстояние, используя stringdist, Выходные данные заменяют входные данные нумерованным списком вместо сравниваемой фактической строки. Это то, что у меня сейчас есть: library(stringdist) a <- c("foo", "bar", "bear", "boat", m…
23 дек '16 в 18:53
2
ответа
Алгоритм поиска расстояния редактирования для всех подстрок
Учитывая 2 строки s а также t, Мне нужно найти для каждой подстроки в s изменить расстояние (расстояние Левенштейна) до t, На самом деле мне нужно знать для каждого i положение в s каково минимальное расстояние редактирования для всех подстрок, начи…
15 ноя '11 в 16:49
1
ответ
Существует ли алгоритм нечеткого поиска, такой как расстояние Левенштейна, специализированный для набора упорядоченных символов?
Я нашел алгоритм (на https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance) и, прочитав немного больше о Левенштейне, понял, что должен быть лучший способ сообщить расстояние редактирования двух строк, если эти строки с…
19 май '16 в 09:56
2
ответа
ipython Pandas: Как я могу сравнить разные строки одного столбца с метрикой расстояния Левенштейна?
У меня есть такая таблица: id name 1 gfh 2 bob 3 boby 4 hgf и т.п. Мне интересно, как я могу использовать метрику Левенштейна для сравнения разных строк моего столбца "имя"? Я уже знаю, что я могу использовать это для сравнения столбцов: L.distance(…
03 апр '15 в 09:26