суббота, 23 апреля 2011 г.

Find sum of elements in the array

Наткнулся на задачу, которую предлагают в Yandex на собеседовании:
Ниже приведены три варианта суммирования чисел с плавающей точкой (предполагается, что числа в массиве только положительные).
double sum1(std::vector<double>& v)
{    
    if (v.empty()) {
        return 0.0;
    }
    for(size_t i = 0; i < v.size() - 1; ++i) {
        std::sort(v.begin()+i, v.end());
        v[i+1] += v[i];
    }
    return v.back();
}
<...>

Остальные варианты пока нам не интересны, их можно посмотреть тут (кстати, в последнем варианте бесконечный цикл). Зачем тут лишняя сортировка ясно сразу — предполагается, что точности double не хватит для расчетов. Ведь если суммировать числа от больших к меньшим, то сумма быстро растёт, и, когда мы дойдём до маленьких чисел, они могут быть денормализованы с огромной ошибкой.

Чтобы оценить о каком порядке ошибки идет речь посмотрим на следующий пример:
const double x = 0.01;
double s = 1000000000.; // initial sum
for (int i = 0; i < 10000; ++i ) {
    s = s + x;
}
const double e = 1000000100. - s;
std::cout << e << std::endl;
На моей машине он выдает результат: 9.53674e-05

Итого, простое суммирование чисел в худшем случае имеет ошибку, которая растет пропорционально $n$, и среднеквадратичную ошибку, которая растет как $\sqrt n$ на случайных данных.

Однако, хочется суммировать без ошибок и при этом делать это не за линейно-логарифмическое время $O(n\log n)$, а за линейное $O(n)$. Это нам позволяет алгоритм автора стандарта IEEE 754, Уильяма Мортона Кэхэна (Kahan). Он разработал алгоритм для минимизации ошибки при сложении чисел в представлении IEEE 754, который был назван в его честь. Предыдущий пример с учетом алгоритма Кэхэна:
const double x = 0.01;
double c = 0; // keep error here, initial error is zero
double s = 1000000000.; // initial sum
for (int i = 0; i < 10000; ++i ) {
    const double y = x - c;
    const double t = s + y;
    c = (t - s) - y; // Beware eagerly optimising compilers!
    s = t;
}
const double e = 1000000100. - s;
std::cout << e << std::endl;
В итоге выдает 0.

При суммировании с компенсацией в худшем случае ошибка не зависит от $n$, поэтому большие числа могут быть сложены с ошибкой, которая зависит только от точности типа с плавающей точкой. Видимо, это то решение, которое ожидается от кандидата.

понедельник, 11 апреля 2011 г.

Autocomplete или как измерить расстояние Левенштейна


На днях встал вопрос сделать функцию для подсказки завершения слов. Самый простой вариант — сравнивать введенную часть слова с первыми буквами слов из словаря и выдавать все слова, у которых совпадает начало. На маленьких словарях это работает, в целом, неплохо, но люди делают опечатки и хотелось бы предлагать исправленные варианты слов, т. е. нужно выдавать похожие слова. Про меру «похожести» последовательностей 0–1 ещё в 1965 году упомянул советский математик Владимир Иосифович Левенштейн, что позже дало имя расстоянию Левенштейна.
Расстояние Левенштейна — это минимальное количество операций вставки, замены и удаления одного символа, необходимых для превращения одной строки в другую.

Это уже почти то, что нужно, но в расстоянии Левенштейна перестановки не учитываются. На наше счастье товарищ Дамерау (Damerau) не только добавил к указанным операциями ещё одну — перестановку двух соседних символов, но и утверждал, что 80% ошибок при наборе текста дают как раз указанные четыре операции. Расстояние, которое учитывает эти операции назвали, как можно догадаться, расстоянием Дамерау–Левенштейна. Результаты этих работ теперь используются не только в бесполезных спеллчекерах, которые убивают грамотность, но и в исследованиях ДНК.

Мне же эти исследования пригодились для решения поставленной задачи. Ниже показана функция на C++, которая вычисляет расстояние Дамерау–Левенштейна:
int damerauLevenshteinDistance( const std::vector<char>& a, const std::vector<char>& b )
{
    const int a_size = static_cast<int>( a.size() );
    const int b_size = static_cast<int>( b.size() );
    const int INF = a_size + b_size;
    std::vector<std::vector<int> > H( a.size()+2, std::vector<int>( b.size()+2 ) );
    H[0][0] = INF;
    for ( int i = 0; i <= a_size; ++i ) { H[i+1][1] = i; H[i+1][0] = INF; }
    for ( int j = 0; j <= b_size; ++j ) { H[1][j+1] = j; H[0][j+1] = INF; }
    
    const int alphabet_size = std::numeric_limits<char>::max();
    std::vector<char> DA( alphabet_size );
    for ( int d = 0; d < alphabet_size; ++d ) DA[d] = 0;
    for ( int i = 1; i <= a_size; ++i ) {
        size_t DB = 0;
        for ( int j = 1; j <= b_size; ++j ) {
            const int i1 = DA[ b[j-1] ];
            const int j1 = DB;
            const int d = (a[i-1]==b[j-1]) ? 0 : 1;
            if ( d == 0 ) DB = j;
            H[i+1][j+1] = std::min( 
                std::min(H[i][j]+d, H[i+1][j]+1), 
                std::min(H[i][j+1]+1, H[i1][j1] + (i-i1-1) + 1 + (j-j1-1) ) );
        }
        DA[ a[i-1] ] = i;
    }
    return H[a.size()+1][b.size()+1];
}
Тема последних дней — поиск Муаммара Каддафи. Расчет расстояния от этого слова (Gadaffi) до всех слов английского словаря размером 329380 слов занимает порядка 2 секунд на моем домашнем Core2Duo 2.13GHz, т. е. функция работает довольно быстро.

Поскольку в моем словаре слов на несколько порядков меньше и выбирает их пользователь, то моя задача оказалась решена. Однако, существуют и другие варианты хранения словарей, например, префиксное дерево (trie), в котором каждый узел хранит первые буквы строк, потом пары букв и так далее. См. картинку из Википедии:
http://en.wikipedia.org/wiki/Trie
В таком дереве поиск подходящих окончаний происходит очень быстро. Этот метод также применяется в спелчекерах (например, встречается сотовых телефонах).

Стоит отметить, что автозавершение слов — это встроенная функция Windows и разработчикам предлагаются интерфейсы IAutoComplete и IACList, пользоваться которыми, на первый взгляд, оказалось не очень удобно и они реализуют самый простой вариант автозавершения, что тоже не подходит.

Ссылки по теме:
  1. SimMetrics — an open source extensible library of Similarity or Distance Metrics, e.g. Levenshtein Distance, L2 Distance, Cosine Similarity, Jaccard Similarity etc.
  2. Damerau–Levenshtein distance
  3. Trie
  4. GNU Aspell is a Free and Open Source spell checker
  5. Implementing an autocompleting Combobox
  6. Using Autocomplete in Windows