Сравнение строк

[ProX_Alex]

Доброго времени суток,

столкнулся с такой проблемой: имею 2 строки, например
("пашек" и "пазек") разница в одну букву(может быть и в 2 и в 3 в редких случаях), так же может быть разница в количестве букв в строках, например("пашек" и "пасзек"), т.е. строки то обозначают одно и тоже слово, однако в разным местах написано по разному, можно ли как то сравнивать эти строки по приблизительно похожему составу букв или как-то по-другому не прибегая к сложным решениям?

[Reskov]

можно посчитать растояния левенштейна
из википедии
wiki
код тоже из англ википедии

public static Int32 DamerauLevenshteinDistance(String source, String target)
{
    if (String.IsNullOrEmpty(source))
    {
        if (String.IsNullOrEmpty(target))
        {
            return 0;
        }
        else
        {
            return target.Length;
        }
    }
    else if (String.IsNullOrEmpty(target))
    {
        return source.Length;
    } 
 
    Int32 m = source.Length;
    Int32 n = target.Length;
    Int32[,] H = new Int32[m + 2, n + 2];
 
    Int32 INF = m + n;
    H[0, 0] = INF;
    for (Int32 i = 0; i <= m; i++) { H[i + 1, 1] = i; H[i + 1, 0] = INF; }
    for (Int32 j = 0; j <= n; j++) { H[1, j + 1] = j; H[0, j + 1] = INF; }
 
    SortedDictionary<Char, Int32> sd = new SortedDictionary<Char, Int32>();
    foreach (Char Letter in (source + target))
    {
        if (!sd.ContainsKey(Letter))
            sd.Add(Letter, 0);
    }
 
    for (Int32 i = 1; i <= m; i++)
    {
        Int32 DB = 0;
        for (Int32 j = 1; j <= n; j++)
        {
            Int32 i1 = sd[target[j - 1]];
            Int32 j1 = DB;
 
            if (source[i - 1] == target[j - 1])
            {
                H[i + 1, j + 1] = H[i, j];
                DB = j;
            }
            else
            {
                H[i + 1, j + 1] = Math.Min(H[i, j], Math.Min(H[i + 1, j], H[i, j + 1])) + 1;
            }
 
            H[i + 1, j + 1] = Math.Min(H[i + 1, j + 1], H[i1, j1] + (i - i1 - 1) + 1 + (j - j1 - 1));
        }
 
        sd[source[i - 1]] = i;
    }
 
    return H[m + 1, n + 1];
}

еще если интересно другой вариант это n-граммы «Если слово А совпадает со словом Б с учетом нескольких ошибок, то с большой долей вероятности у них будет хотя бы одна общая подстрока длины N».
т.е. можем сравнивать по триграммам например и смотреть сколько триграмм совпало

еще можно подключить библиотеку спеллчекинга и просто исправлять ошибки в словах

[ProX_Alex]

Reskov, спасибо за направление куда копать.
Про библиотеку понравилось, однако нашёл http://www.spellcheck.net , но русский не поддерживается. Может быть Есть что подказать по этому поводу. Хотя скорее всего такие слова не будут исправляться этой библиотекой, потому что это фамилии, но всё таки хотелось бы по простому =), поэтому попытка не пытка.

[Stilet]

Это по-моему называется сравнением по релевантности.
Алгоритмы в инете есть, когда-то находил парочку.
Даже когда-то отсебятинку лепил:

// sdf.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"
#include <string>

using namespace std;

/*
 s - Исходная строка
 q - сторка совпадения
 perc - процент совпадения
*/
int relevatio(string s, string q, int perc){
	int r=0;
	int k=0;
	for(int i=0;i<q.length();i++){
		bool found=false;
		for(;k<s.length();k++){
			if(q[i]==s[k]){
				r++;
				break;
				found=true;
			}
		}
		if(found) k=i;
	}
	r=r*100/s.length(); //100/len=x/k
	return r>perc;
}

int _tmain(int argc, _TCHAR* argv[])
{
	string s[5]={"petrpetrov","ivanivanov","vetrovalexey","olegpestov","petyaivanov"};
	for(int i=0;i<5;i++){
		bool k=relevatio(s[i].c_str(),"petrov",20);
		// Если процент совпадения по последовательности всплытия символов более указаноого - строка подходит.
		printf("%s\t%s\n",s[i].c_str(),(k)?"Yes":"No");

	}
	getchar();
	return 0;
}

P.S. Это конечно не шарп но надеюсь принцип понятен.

[Reskov]

Про библиотеку... на гуглил... там есть и русский словарь к нему

http://sourceforge.net/projects/nhunspell/files/
http://code.google.com/p/hunspell-ru...1.zip&can=2&q=

и попростому расстояние левештейна... смотрите составляете словарь фамилий... если их немного (до 10000) можете для каждого считать растояние левенштейна и выбирать фамилию с наименьшим расстоянием...
если слов много тогда разбиваете слова по три граммам и заносите их в словарь этих триграмм, потом тоже выбираете слово с наибольшим совпадением трехграмм
на самом деле все это пишется довольно легко
а если будете использовать спел чекер то вам нужно просто составить для него словарь фамилий...