Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.96
Union
 Аватар для Union
17 / 17 / 2
Регистрация: 16.08.2010
Сообщений: 252
26.05.2012, 01:26     Степень похожести двух строк (слов). Расстояние Левенштейна #1
Имеется два массива, в которых содержатся слова. Одно слово из базы, второе получено от человека и может содержать ошибки. К примеру:
C++
1
2
char a[]="leader";
char b[]="lider";
Необходимо определить расстояние Левенштейна, то есть сколько символов в слове отличаются, и вывести процентное соответствие (то есть какова вероятность что введенное слово является выбранным из базы словом).

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

C++ Предложение из двух слов
расстояние между строк C++
C++ Сравнение двух слов
Строка: Добавить в строковый класс функцию, которая создает строку, содержащую пересечение двух строк, то есть общие символы для двух строк. C++
Даны координаты двух точек. Вычислить расстояние между ними C++
Схожесть текстов (расстояние Левенштейна) C++
C++ Сравнения слов в двух строках
Функция, которая вернет номера двух из трех заданных точек на плоскости, расстояние между которыми минимально C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 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/533150...4375c1a417ed15
Yandex
Объявления
26.05.2012, 14:18     Степень похожести двух строк (слов). Расстояние Левенштейна
Ответ Создать тему
Опции темы

Текущее время: 09:56. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru