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\), поэтому большие числа могут быть сложены с ошибкой, которая зависит только от точности типа с плавающей точкой. Видимо, это то решение, которое ожидается от кандидата.

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), в котором каждый узел хранит первые буквы строк, потом пары букв и так далее. См. картинку из Википедии:

В таком дереве поиск подходящих окончаний происходит очень быстро. Этот метод также применяется в спелчекерах (например, встречается сотовых телефонах).

Стоит отметить, что автозавершение слов — это встроенная функция 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