Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.78/23: Рейтинг темы: голосов - 23, средняя оценка - 4.78
Union
17 / 17 / 0
Регистрация: 16.08.2010
Сообщений: 252
1

Степень похожести двух строк (слов). Расстояние Левенштейна

26.05.2012, 01:26. Просмотров 4381. Ответов 1
Метки нет (Все метки)

Имеется два массива, в которых содержатся слова. Одно слово из базы, второе получено от человека и может содержать ошибки. К примеру:
C++
1
2
char a[]="leader";
char b[]="lider";
Необходимо определить расстояние Левенштейна, то есть сколько символов в слове отличаются, и вывести процентное соответствие (то есть какова вероятность что введенное слово является выбранным из базы словом).

(Расстояние Левенштейна - это минимальное количество вставок, замен и удалений символов, необходимое для преобразования a в b.)
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.05.2012, 01:26
Ответы с готовыми решениями:

Схожесть текстов (расстояние Левенштейна)
Программа, которая сравнивает 2 теста на схожесть из 1.txt и 2.txt нужно что бы...

Строка: Добавить в строковый класс функцию, которая создает строку, содержащую пересечение двух строк, то есть общие символы для двух строк.
Добавить в строковый класс функцию, которая создает строку, содержащую...

Код Левенштейна
Здравствуйте. Поставили такую задачу - реализовать код Левенштейна. Очень...

расстояние между строк
Несколько дней ломаю моск никак не получается. Пож оч нужно для допуска к...

Найти номера двух точек, расстояние между которыми наибольшее
Надеюсь сможет кто-нибудь помочь, буду премного благодарен :) 1. Даны...

1
gray_fox
What a waste!
1554 / 1259 / 166
Регистрация: 21.04.2012
Сообщений: 2,636
Завершенные тесты: 3
26.05.2012, 14:18 2
Вагнер-Фишер не устраивает?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
 
 
typedef double cost_type;
 
cost_type insertion_cost(std::string::value_type ch) {
   return 1;
}
 
cost_type removal_cost(std::string::value_type ch) {
   return 1;
}
 
cost_type update_cost(std::string::value_type lhs, std::string::value_type rhs) {
   return lhs == rhs ? 0 : 1;
}
 
cost_type edit_distance(std::string const& from, std::string const& to) {
   std::vector<std::vector<cost_type>> costTable(from.length() + 1, std::vector<cost_type>(to.length() + 1));
   
   costTable[0][0] = 0;
   
   for (std::size_t j = 0; j != to.length(); ++j) {
      costTable[0][j + 1] = costTable[0][j] + insertion_cost(to[j]); 
   }
     
   for (std::size_t i = 0; i != from.length(); ++i) {
      costTable[i + 1][0] = costTable[i][0] + removal_cost(from[i]);
      
      for (std::size_t j = 0; j != to.length(); ++j) {
         costTable[i + 1][j + 1] = std::min(std::min(
            costTable[i + 1][j] + insertion_cost(to[j]),
            costTable[i][j + 1] + removal_cost(from[i])),
            costTable[i][j] + update_cost(from[i], to[j]));
      }
   }
   
   return costTable[from.length()][to.length()];
}
 
 
int main() {
   std::cout << edit_distance("leader", "lider") << std::endl;
}
http://liveworkspace.org/code/53315054b81a3aef784375c1a417ed15
3
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.05.2012, 14:18

Даны координаты двух точек. Вычислить расстояние между ними
Начал изучать С++ совсем не давно. Стал разбираться после чтения некоторых...

Необходим алгоритм сравнения строк: вычисление коэффициента "похожести" двух строк в диапазоне от 0 до 1
очень необходима эта или подобная обработка http://infostart.ru/public/146559/

Расстояние между двумя строками. Функция Левенштейна
Имеется программа для нахождения расстояния между двумя строками.На форме...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru