Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.96
Union
17 / 17 / 2
Регистрация: 16.08.2010
Сообщений: 252
#1

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

26.05.2012, 01:26. Просмотров 3760. Ответов 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
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Степень похожести двух строк (слов). Расстояние Левенштейна (C++):

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

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

Код Левенштейна - C++
Здравствуйте. Поставили такую задачу - реализовать код Левенштейна. Очень нужно, помогите пожалуйста) Нашел вот этот алгоритм Тут

расстояние между строк - C++
Несколько дней ломаю моск никак не получается. Пож оч нужно для допуска к экз!!!! Расстояние между k-й и l-й строками матрицы...

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

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

1
gray_fox
What a waste!
1522 / 1227 / 70
Регистрация: 21.04.2012
Сообщений: 2,565
Завершенные тесты: 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 - 1С
очень необходима эта или подобная обработка http://infostart.ru/public/146559/

Расстояние между двумя строками. Функция Левенштейна - Delphi
Имеется программа для нахождения расстояния между двумя строками.На форме находятся два поля Edi1 и Edit2 и метка Label1.При запуске выдает...

Алгоритм нахождения “похожести” двух значений - VBA
Всем здравствуйте. Работая с большим кол-вом информации в Excel, я всегда сталкивался с проблемой неразличения Excel’ем двух похожих...

Выделение и сравнение слов из двух строк - C (СИ)
По какой причине не работает функция proces? Подскажите, пожалуйста #include &lt;stdio.h&gt; #include &lt;string.h&gt; #include &lt;conio.h&gt; ...


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

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

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