Поиск медианы и обобщенной медианы

[Kostia]

Заранее извинюсь если не туда запостил.

Имеем:
эталонное слово: например "кириллица"
и набор слов с 50% ошибок типа замена, удаление, вставка и перестановка двух рядом стоящих символов

string word = "кириллица", word50;
    srand(time(0));
    int r;
    for(int i = 0; i < 10; i++){
        word50 =  word;
        for(int j = 0; j < word.size()/2; j++){
            switch(rand()%4){
                case 0:
                    word50[rand()%word50.size()] = 'а' + rand()%32; //замена
                    break;
                case 1:
                    word50.insert(rand()%word50.size(),1,'а'+rand()%32); //вставка
                    break;
                case 2:
                    word50.erase(rand()%(word50.size()-1),1); //удаление
                    break;
                case 3:
                    r = rand()%(word50.size()-1);
                    swap(word50[r],word50[r+1]);
                    break;
            }
        }
        cout << word50 << " " << distance("кириллица",word50) << "\n";
    }

distance - расстояние Левенштейна http://ru.wikipedia.org/wiki/%D0%A0%...1%D1%82%D0%BE… 9%D0%BD%D0%B0

double replacement(char a, char b){
    if(a==b) return 0;
    if(((a=='е')||(a=='и'))&&((b=='е')||(b=='и'))) return 0.4;
    return 1.0;
}

double removal(char a){
    if(a=='ъ') return 0.2;
    if(a=='ь') return 0.2;
    if(a=='й') return 0.2;
    return 1.0;
}

double insertion(char a){
    if(a=='ъ') return 0.2;
    if(a=='ь') return 0.2;
    if(a=='н') return 0.7;
    return 1.0;
}

double transposition(char a, char b)
{
    if(a==b) return 0.0;
    return 0.5;
}

double distance(string a, string b){
    double **D = new double*[a.size()+1];
    double m1,m2,m3,m4;
    for(int i = 0; i < a.size()+1; i++){
        D[i] = new double[b.size()+1];
        memset(D[i],0,sizeof(double)*(b.size()+1));
    }
    D[0][0] = 0.0;
    for(int i = 0; i < a.size(); i++)D[i+1][0] = D[i][0] + removal(a[i]);
    for(int i = 0; i < b.size(); i++)D[0][i+1] = D[0][i] + insertion(b[i]);
    for(int i = 0; i < a.size(); i++)
        for(int j = 0; j < b.size(); j++){
            m1 = D[i][j] + replacement(a[i],b[j]);
            m2 = D[i+1][j] + insertion(b[j]);
            m3 = D[i][j+1] + removal(a[i]);
            D[i+1][j+1] = min(min(m1,m2),m3);
            if((i>0)&&(j>0)&&(a[i]==b[j-1])&&(a[i-1]==b[j])){
                m4 = D[i-1][j-1] + transposition(a[i],b[j]);
                D[i+1][j+1] = min(D[i+1][j+1], m4);
            }
        }
    return D[a.size()][b.size()];
}

replacement, replacement, removal, transposition - функции возвращают цену действия(будут доработаны, а пока для тестов такие)

Не могу найти описание подхода для более менее быстрого поиска медианы, такой что
distance(X1, m) и distance(X2, m) минимальны
И обобщенной медианы, такой что расстояние до всех остальных медиан минимально.

С обычными вещественными векторами все элементарно, а вот со строка заморочка выходит =(

[Kostia]

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

[Utkin]

и набор слов с 50% ошибок типа замена, удаление, вставка и перестановка двух рядом стоящих символов

Приведите примеры слов.

[ds.Dante]

[упс, невнимательно сначала прочитал]

Если есть матрица преобразований, то медиана должна быть на полпути от одного угла матрицы до противоположного.

[Kostia]

кишивлица 2
киллиац 2.5
прллица 3
кирлиилца 1
кигрилкицза 3
кирлзилциа 3.5
лирилица 2
иришлиац 2.5
крилитлзца 3
кирилла 2

Числа справа, это расстояние до эталонного слова "кириллица"

Медиана должна минимизировать такую сумму:
D += distance(x[i], m)

А медиана абсолютно минимизирующая эту сумму, есть обобщенная медиана.

Меня что-то заклинило сначала найти медианы между парами {{1,2},{2,3}...{n-1,n}} дальше найти обобщенную медиану, которая минимизирует расстояние до всех остальных медиан. И как бы она и будет обобщенной медианой и будет минимизировать первую сумму, исходя из того что обычные медианы ее тоже минимизируют(но только для двух соседних).
Тут загвоздка, если искать все медианы между каждой парой, то потребуется уйма процессорного времени, n*n-n штук если не ошибаюсь, то тогда можно гарантировать что мы найдем обобщенную медиану, а в случае пар, которые я указал, этого гарантировать нельзя(но думаю и такой точности будет достаточно).

Если есть матрица преобразований, то медиана должна быть на полпути от одного угла матрицы до противоположного.

Да это подойдет для пары слов, т.е. для поиска обычных медиан

[Kostia]

Вот что нарыл, но не могу провернуть это в голове:
страница 40, текст не копируется =(
http://window.edu.ru/resource/598/64....3_cB352-4.pdf

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

[ds.Dante]

Можно такой вариант: для каждой пары слов находим минимальный путь со всеми промежуточными состояниями. И из всех этих промежуточных слов выбираем самое медианное. Алгоритм получается сложный (n^3 * m^2), но мне почему-то кажется, что результат должен получиться строго точный.

[Kostia]

Поиск обобщенной медианы отложил до лучших времен, пока достаточной простой медианы.
Теперь задача состоит в том чтобы правильно(более или менее) заполнить матрицы вероятностей ошибок разного рода. И если кому не лень, то вы можете мне помочь.

Нужно чтобы вы написали какой либо текст, но во время его написания не исправляли своих опечаток(желательно чтобы были в тексте символы только русского алфавита, знаки препинания на ваше усмотрение). Сохраните текст, а затем исправьте в нем ошибки. Оба теста отправьте мне на мыло icetomcat(собака)gмыло.com

Важно чтобы вы не переписывали текст, а брали все из головы. Например ответив на какой либо вопрос или просто мысли вслух.

1. Чем хорошо или плохо современное образование
2. Феминизм, что вы об этом думаете
...

Чем больше людей откликнется( и чем больше очепяток будет xD), тем больше объективности будет в полученных матрицах.