Как реализовать выравнивание через трассировку для расстояния редактирования левенштейна

Определение

Расстояние Левенштейна между двумя струнами (длины и соответственно) определяется как где
а,б{\ displaystyle a, b}|а|{\ displaystyle | a |}|б|{\ displaystyle | b |}лев⁡(а,б){\ displaystyle \ operatorname {lev} (a, b)}

лев⁡(а,б)знак равно{|а| если |б|знак равно,|б| если |а|знак равно,лев⁡(хвост⁡(а),хвост⁡(б)) если азнак равноб1+мин{лев⁡(хвост⁡(а),б)лев⁡(а,хвост⁡(б))лев⁡(хвост⁡(а),хвост⁡(б)) иначе,{\ displaystyle \ operatorname {lev} (a, b) = {\ begin {cases} | a | & {\ text {if}} | b | = 0, \\ | b | & {\ text {if}} | a | = 0, \\\ operatorname {lev} {\ big (} \ operatorname {tail} (a), \ operatorname {tail} (b) {\ big)} & {\ text {if}} a = b \\ 1+ \ min {\ begin {cases} \ operatorname {lev} {\ big (} \ operatorname {tail} (a), b {\ big)} \\\ operatorname {lev } {\ big (} a, \ operatorname {tail} (b) {\ big)} \\\ operatorname {lev} {\ big (} \ operatorname {tail} (a), \ operatorname {tail} (b) {\ big)} \\\ end {case}} & {\ text {в противном случае}} \ end {case}}}

где некоторой строки — это строка, состоящая из всех символов , кроме первого , и — это th символ строки , считая от 0 .
хвост{\ displaystyle \ operatorname {tail}}Икс{\ displaystyle x}Икс{\ displaystyle x}Иксп{\ Displaystyle х }п{\ displaystyle n}Икс{\ displaystyle x}

Обратите внимание, что первый элемент в минимуме соответствует удалению (от до ), второй — вставке, а третий — замене.
а{\ displaystyle a}б{\ displaystyle b}

Это определение прямо соответствует .

Пример

Отредактируйте матрицу расстояний для двух слов, используя стоимость замены как 1 и стоимость удаления или вставки как 0,5

Например, расстояние Левенштейна между «котенком» и «сидящим» равно 3, поскольку следующие 3 правки меняют одно на другое, и нет способа сделать это с менее чем тремя правками:

1. k itten → s itten (замена «k» на «s»),
2. sitt e n → sitt i n (замена «i» на «e»),
3. sittin → sittin g (вставка буквы «g» в конце).

Верхняя и нижняя границы

Расстояние Левенштейна имеет несколько простых оценок сверху и снизу. Это включает:

• Это как минимум разница в размерах двух струн.
• Это не больше длины более длинной струны.
• Он равен нулю тогда и только тогда, когда строки равны.
• Если струны имеют одинаковый размер, расстояние Хэмминга является верхней границей расстояния Левенштейна. Расстояние Хэмминга — это количество позиций, в которых соответствующие символы в двух строках различаются.
• Расстояние Левенштейна между двумя струнами не больше суммы их расстояний Левенштейна от третьей струны ( неравенство треугольника ).

Пример, когда расстояние Левенштейна между двумя струнами одинаковой длины строго меньше расстояния Хэмминга, дается парой «изъян» и «лужайка». Здесь расстояние Левенштейна равно 2 (удалить букву «f» спереди, вставить «n» в конце). Расстояние Хэмминга равно 4.

Алгоритм нечёткого поиска

Таким образом, суть алгоритма нечёткого поиска может быть сведена к следующему:

1. Вычислить метафон поискового запроса.
2. Найти все слова в словаре в БД по метафону с расстоянием Левенштейна (или Дамерау-Левенштейна) < 2 символов.
3. Если ничего не найдено — юзер сделал слишком много ошибок в слове, прекращаем мучить БД и пишем, что юзер идёт в баню ничего не найдено.
4. Если найдено 1 слово — возвращаем его.
5. Если найдено > 1 слова — рафинируем: находим процент похожести поискового запроса с каждым найденным словом из словаря в БД; находим максимальный процент похожести; возвращаем все слова с этим процентом (на случай, если несколько слов будут иметь одинаковый процент, который окажется максимальным).

При каждом поиске необходимо будет рассчитывать расстояние Левенштейна. Для этого нужно найти самую быструю имплементацию алгоритма для MySQL.

Оптимизация запросов SELECT

Не читайте больше данных, чем надо. Не используйте *

Если ваше приложение позволяет пользователям выполнять запросы, но вы не можете отсечь лишние сотни и тысячи возвращаемых строк, используйте оператор TOP внутри инструкции SELECT. 

Не возвращайте клиенту большее количество столбцов или строк, чем действительно необходимо (Не используй * в Select). 

Как можно раньше отфильтруйте данные. Не нужно выполнять большой тяжелый подзапрос для  всех строк таблицы. Сначала отфильтруйте нужные строки.

Корректно используйте JOIN

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

Для лучшей производительности, столбцы, используемые в объединениях должны иметь одинаковые типы данных. И если возможно, это должны быть числовые типы данных, вместо символьных типов.

Избегайте объединять таблицы по столбцам с малым числом уникальных значений. Если столбцы, используемые при объединениях, имеют мало уникальных значений, то SQL сервер будет просматривать всю таблицу, даже если по данному столбцу существует индекс. Для наилучшей производительности объединение таблиц должно производится по столбцам с уникальными индексами.

Если Вы должны регулярно объединять четыре или более таблиц, для получения recordset’а, попробуйте денормализовать таблицы так, чтобы число таблиц, участвующих в объединении уменьшилось. Часто, при добавлении одного или двух столбцов из одной таблицы в другую, объединения могут быть уменьшены.

Тип JOIN используйте только тот, который вернет вам НЕОБХОДИМЫЕ данные без каких-либо дублей или лишней информации (или совсем отказаться от join). Т.е. не нужно получать всех пользователей таким образом: 

В этом случае вы получите много повторов пользователей

Сортировка в SELECT

Самой ресурсоемкой сортировкой является сортировка строк.

При объявлении полей всегда следует использовать размер, который нужен, и не выделять лишние байты про запас.

Группирование в SELECT

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

По возможности лучше использовать Where вместо Having, т.к. это уменьшает количество строк для группировки на ранней стадии. 

Если требуется группирование, но без использования агрегатных функций (COUNT(), MIN(), MAX и т.д.), разумно использовать DISTINCT.

Ограничить использование DISTINCT

Эта команда исключает повторяющиеся строки в результате. Команда требует повышенного времени обработки. Лучше всего комбинировать с LIMIT.

Ограничить использование SELECT для постоянно изменяющихся таблиц.

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

Оптимизация WHERE в запросе SELECT

Если where состоит из условий, объединенных AND,  они должны располагаться в порядке возрастания вероятности истинности данного условия. Чем быстрее мы получим false  в одном из условий — тем меньше условий будет обработано и тем быстрее выполняется запрос. 

Если where состоит из условий, объединенных OR,  они должны располагаться в порядке уменьшения вероятности истинности данного условия. Чем быстрее мы получим true  в одном из условий — тем меньше условий будет обработано и тем быстрее выполняется запрос. 

Исопльзуйте IN вместо OR. Операция IN работает гораздо быстрее, чем серия OR.  Запрос «… WHERE column1 = 5 OR column1 = 6» медленнее чем «…WHERE column1 IN (5, 6)». 

Используйте Exists вместо Count >0 в подзапросах. Используйте where exists (select id from t1 where id = t.id) вместо where count(select id from t1 where id=t.id) > 0

LIKE. Эту операцию следует использовать только при крайней необходимости, потому что лучше и быстрее использовать поиск, основанный на full-text индексах. 

C++[править]

Имплементация использует ∼ min(m,n){\displaystyle \sim ~min(m,n)} памяти:

#include<algorithm>
#include<vector>

template<typename T>
typename T::size_typeLevenshteinDistance(constT&source,
constT&target){
if(source.size()>target.size()){
returnLevenshteinDistance(target,source);
}

usingTSizeType=typename T::size_type;
constTSizeTypemin_size=source.size(),max_size=target.size();
std::vector<TSizeType>lev_dist(min_size+1);

for(TSizeTypei=;i<=min_size;++i){
lev_disti=i;
}

for(TSizeTypej=1;j<=max_size;++j){
TSizeTypeprevious_diagonal=lev_dist],previous_diagonal_save;
++lev_dist];

for(TSizeTypei=1;i<=min_size;++i){
previous_diagonal_save=lev_disti];
if(sourcei-1==targetj-1]){
lev_disti=previous_diagonal;
}else{
lev_disti=std::min(std::min(lev_disti-1],lev_disti]),previous_diagonal)+1;
}
previous_diagonal=previous_diagonal_save;
}
}

returnlev_distmin_size];
}

Пример использования:

// Может быть использован любой подходящий контейнер (напр. std::vector).
// В нашем примере использованы строки:
...
conststd::stringsrc="125";
conststd::stringdst="521";
conststd::string::size_typedistance=LevenshteinDistance(src,dst);
...

Имплементация обобщённого расстояния Левенштейна с произвольными стоимостями вставки, удаления и замены символа:

#include<algorithm>
#include<vector>

template<typename T>
typename T::size_typeGeneralizedLevenshteinDistance(constT&source,
constT&target,
typename T::size_typeinsert_cost=1,
typename T::size_typedelete_cost=1,
typename T::size_typereplace_cost=1){
if(source.size()>target.size()){
returnGeneralizedLevenshteinDistance(target,source,delete_cost,insert_cost,replace_cost);
}

usingTSizeType=typename T::size_type;
constTSizeTypemin_size=source.size(),max_size=target.size();
std::vector<TSizeType>lev_dist(min_size+1);

lev_dist=;
for(TSizeTypei=1;i<=min_size;++i){
lev_disti=lev_disti-1+delete_cost;
}

for(TSizeTypej=1;j<=max_size;++j){
TSizeTypeprevious_diagonal=lev_dist],previous_diagonal_save;
lev_dist+=insert_cost;

for(TSizeTypei=1;i<=min_size;++i){
previous_diagonal_save=lev_disti];
if(sourcei-1==targetj-1]){
lev_disti=previous_diagonal;
}else{
lev_disti=std::min(std::min(lev_disti-1+delete_cost,lev_disti+insert_cost),previous_diagonal+replace_cost);
}
previous_diagonal=previous_diagonal_save;
}
}

returnlev_distmin_size];
}

Как одно изменение конфигурации PostgreSQL улучшило производительность медленных запросов в 50 раз

В связи с санкциями и другими событиями сейчас все более и более актуальна тема перевода ПО компаний на отечественное и свободное программное обеспечение. Одной из самых востребанных СУБД на рынке на данный момент является PostgreSQL — надежная, высокопроизводительная и хорошо масштабируемая СУБД, которая является прямым конкуретном таким крупным компаниям с их топовыми продуктами, как Oracle, IBM и Microsoft. Однако каждый, кто переходит на PostgreSQL, сталкивается с трудностями, прежде всего с настройкой и производительностью. Не обошли проблемы с производительностью «слоника» и меня. Предлагаю вашему вниманию перевод статьи «How a single PostgreSQL config change improved slow query performance by 50x» автора Pavan Patibandla, которая мне помогла улучшить производительность PostgreSQL.

Сервер 1С:Предприятие на Ubuntu 16.04 и PostgreSQL 9.6, для тех, кто хочет узнать его вкус. Рецепт от Капитана

Если кратко описать мое отношение к Postgres: Использовал до того, как это стало мейнстримом.
Конкретнее: Собирал на нем сервера для компаний среднего размера (до 50 активных пользователей 1С).
На настоящий момент их набирается уже больше, чем пальцев рук пары человек (нормальных, а не фрезеровщиков).
Следуя этой статье вы сможете себе собрать такой же и начать спокойную легальную жизнь, максимально легко сделать первый шаг в мир Linux и Postgres.
А я побороться за 1. Лучший бизнес-кейс (лучший опыт автоматизации предприятия на базе PostgreSQL).
Если, конечно, статья придется вам по вкусу.

Обработки для проведения сценарного нагрузочного тестирования на примере конфигурации ЗУП версии 3.1.1.91

Обработки предназначены  для проведения сценарного нагрузочного тестирования, включая  пример описанного  сценария  с обработками (epf) —  ГлавныйРасчетчик, Кадровик, Расчетчик, Табельщик.
Обработка будет полезна прежде всего тому, кто внедряет решение на базе конфигурации 1С «Зарплата и Управления персоналом» с необходимостью воспроизвести определенный сценарий с заданным количеством пользователей для расчета, а также возможность посмотреть, какая будет при этом нагрузка на ваше оборудование и скорость выполнения операций с учетом блокировок СУБД.
Также это будет интересно тем, кто хочет прощупать, как на практике пользоваться конфигурацией «Тест Центр», входящий в состав пакета 1С:КИП.

2 стартмани

JavaScript[править]

/**
 * @param {string} s1 Исходная строка
 * @param {string} s2 Сравниваемая строка
 * @param {object}  Веса операций { , , ,  }
 * @return {number} Расстояние Левенштейна
 */
function levenshtein(s1, s2, costs) {
    var i, j, l1, l2, flip, ch, chl, ii, ii2, cost, cutHalf;
    l1 = s1.length;
    l2 = s2.length;

    costs = costs || {};
    var cr = costs.replace || 1;
    var cri = costs.replaceCase || costs.replace || 1;
    var ci = costs.insert || 1;
    var cd = costs.remove || 1;

    cutHalf = flip = Math.max(l1, l2);

    var minCost = Math.min(cd, ci, cr);
    var minD = Math.max(minCost, (l1 - l2) * cd);
    var minI = Math.max(minCost, (l2 - l1) * ci);
    var buf = new Array((cutHalf * 2) - 1);

    for (i = ; i <= l2; ++i) {
        bufi = i * minD;
    }

    for (i = ; i < l1; ++i, flip = cutHalf - flip) {
        ch = s1i];
        chl = ch.toLowerCase();

        bufflip = (i + 1) * minI;

        ii = flip;
        ii2 = cutHalf - flip;

        for (j = ; j < l2; ++j, ++ii, ++ii2) {
            cost = (ch === s2j ?   (chl === s2jtoLowerCase()) ? cri  cr);
            bufii + 1 = Math.min(bufii2 + 1 + cd, bufii + ci, bufii2 + cost);
        }
    }
    return bufl2 + cutHalf - flip];
}

Пример использования:

var diff = levenshtein('Hello', 'HelA_1');

Выбираем имплементацию расстояния Левенштейна для MySQL

Как было отмечено раннее, на быстроту будут проверяться три имплементации — запрос Лести, функция Раста и функция Торреса.

Для тестов будут использоваться 5 слов (а точнее, их ошибочное написание), 3 из них на кириллице, и 2 на латинице:

№	Правильное написание	Его метафон	Неправильное написание	Его метафон	Левенштейн метафонов
1.	Александровск-Сахалинский	ALKSNTRFSKSHLNSK	Аликсандравск-саголинзкий	ALKSNTRFSKSKLNSK	1
2.	Семикаракорск	SMKRKRSK	Семикораковск	SMKRKFSK	1
3.	Чаренцаван	XRNTSFN	Черенцева	XRNTSF	1
4.	Bounounbougoula	BNNBKL	Bonunboguva	BNNBKF	1
5.	Kampong Tenaki Kawang	KMPNKTNKKWNK	Kampontenaki Kavang	KMPNTNKKFNK	2

В последнем слове намеренно было сделано больше ошибок, чтобы расстояние Левенштейна было в 2 символа. Если каждый способ работает правильно, при поиске последнего слова каждый раз будет возвращаться 0 строк.

Запрос Лести

В конце статьи автор предлагает PHP-функцию для автоматизации составления таких SQL-запросов. Эта функция изменена применительно для нашего поиска по метафонам, но принцип оставлен тот же:

№ слова	t для LIKE с «_», сек	Найдено	t для LIKE с «%», сек	Найдено
1.	24.2	1	24.6	1
2.	14.1	1	14.8	4
3.	11.9	188	12.3	224
4.	11.9	70	12.8	87
5.	18.1	19.6

Чем длиннее слово, тем больше времени нужно для поиска похожих метафонов (что очевидно), но, в то же время, — чем длиннее слово, тем меньше времени тратится на каждую букву (что не очевидно). Предположим, что $inline$t$inline$ — общее время, затраченное на поиск похожих метафонов, а $inline$n$inline$ — общее количество букв в метафоне, похожести которого мы искали; если первое слово короче второго ($inline$n_1 < n_2$inline$) и, соответственно, общее время, затраченное на поиск похожих метафонов для первого слова меньше, чем для второго ($inline$t_1 < t_2$inline$), то

$$display$$frac{t_1}{n_1} > frac{t_2}{n_2}$$display$$

Также ожидался резкий всплеск во времени при замене шаблона поиска «_» на «%», но общее время увеличивалось в пределах 2-8%.

Функция Раста

Попробуем найти все слова с расстоянием Левенштейна в 1 символ:

Поиск похожих метафонов для четвёртого названия (у которого самый короткий метафон) дал такие же результаты, как и при поиске с помощью LIKE с шаблоном поиска «_», однако занял ~66 минут, поэтому было решено не продолжать тестировать остальные слова.

Функция Торреса

Установим универсальную верхнюю границу для всех метафонов из нашего теста — 20 символов, и попробуем найти все слова с расстоянием Дамерау-Левенштейна в 1 символ:

Результаты:

№ слова	t для ф-ии Торреса, сек	Найдено
1.	11.24	1
2.	9.25	1
3.	9.19	173
4.	8.3	86
5.	11.57

Функция Торреса показала превосходные результаты в сравнении с запросом Лести и особенно в сравнении с функцией Раста. Второй плюс — Торрес использовал расширенный алгоритм Дамерау-Левенштейна, где к операциям вставки, удаления и замены добавлена операция транспозиции. Сравним результаты функции Торреса и запроса Лести:

№ слова	t для запроса Лести, сек	t для ф-ии Торреса, сек	Запрос Лести, найдено слов	Ф-я Торреса, найдено слов
1.	24.2	11.24	1	1
2.	14.1	9.25	1	1
3.	11.9	9.19	188	173
4.	11.9	8.3	70	86
5.	18.1	11.57

Разница в количестве возвращаемых строк может быть объяснена разницей в использованных алгоритмах (Левенштейна и Дамерау-Левенштейна для запроса Лести и функции Торреса соответственно). В 5 случаях из 5 победителем стала функция Торреса, поэтому она и будет применяться в завершающей реализации на PHP, где полученный результат рафинируется функцией similar_text.

Формула[править]

Будем считать, что элементы строк нумеруются с первого, как принято в математике, а не нулевого.

Пусть и  — две строки (длиной и соответственно) над некоторым алфавитом, тогда редакционное расстояние можно подсчитать по следующей рекуррентной формуле:

, где

возвращает наименьший из аргументов.

Доказательствоправить

Рассмотрим формулу более подробно. Здесь  — расстояние между префиксами строк: первыми символами строки и первыми символами строки . Для нашей динамики должен выполняться принцип оптимальности на префиксе. Очевидно, что редакционное расстояние между двумя пустыми строками равно нулю. Так же очевидно то, что чтобы получить пустую строку из строки длиной , нужно совершить операций удаления, а чтобы получить строку длиной из пустой, нужно произвести операций вставки. Осталось рассмотреть нетривиальный случай, когда обе строки непусты.

Для начала заметим, что в оптимальной последовательности операций, их можно произвольно менять местами. В самом деле, рассмотрим две последовательные операции:

• Две замены одного и того же символа — неоптимально (если мы заменили на , потом на , выгоднее было сразу заменить на ).
• Две замены разных символов можно менять местами
• Два стирания или две вставки можно менять местами
• Вставка символа с его последующим стиранием — неоптимально (можно их обе отменить)
• Стирание и вставку разных символов можно менять местами
• Вставка символа с его последующей заменой — неоптимально (излишняя замена)
• Вставка символа и замена другого символа меняются местами
• Замена символа с его последующим стиранием — неоптимально (излишняя замена)
• Стирание символа и замена другого символа меняются местами

Пускай кончается на символ , кончается на символ . Есть три варианта:

1. Символ «а», на который кончается , в какой-то момент был стёрт. Сделаем это стирание первой операцией. Тогда мы стёрли символ , после чего превратили первые символов в (на что потребовалось операций), значит, всего потребовалось операций
2. Символ , на который кончается , в какой-то момент был добавлен. Сделаем это добавление последней операцией. Мы превратили в первые символов , после чего добавили . Аналогично предыдущему случаю, потребовалось операций.
3. Оба предыдущих утверждения неверны. Если мы добавляли символы справа от финального , то чтобы сделать последним символом , мы должны были или в какой-то момент добавить его (но тогда утверждение 2 было бы верно), либо заменить на него один из этих добавленных символов (что тоже невозможно, потому что добавление символа с его последующей заменой неоптимально). Значит, символов справа от финального мы не добавляли. Самого финального мы не стирали, поскольку утверждение 1 неверно. Значит, единственный способ изменения последнего символа — его замена. Заменять его 2 или больше раз неоптимально. Значит,
   1. Если , мы последний символ не меняли. Поскольку мы его также не стирали и не приписывали ничего справа от него, он не влиял на наши действия, и, значит, мы выполнили операций.
   2. Если , мы последний символ меняли один раз. Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить операций, значит, всего потребуется операций.

Оптимизация структуры таблиц SQL Server

Разбивайте сложные таблицы на несколько, помните, чем больше в вашей таблице столбцов и тяжелых типов (nvarchar(max)), тем тяжелее по ней проход. Если некоторые данные не всегда используются в select с ней, выносите их отдельно в таблицу и связывайте через FK

Выберите правильные типы данных. Всегда выбирайте самый маленький тип для данных, которые Вы должны хранить в столбце.

Если текстовые данные в столбце имеют разную длину, используйте тип  данных NVARCHAR вместо NCHAR.

Не используйте NVARCHAR или NCHAR типы данных, если Вы не должны сохранить 16-разрядные символьные данные (UNICODE). Они требуют в два раза больше места, чем CHAR и VARCHAR, что повышает расходы времени на ввод-вывод (но если у вас кириллица, то без NVARCHAR не обойтись).

Если Вы должны хранить большие строки данных и их длина меньше чем 8,000 символов, используют тип данных NVARCHAR вместо TEXT. Текстовые поля требуют больше ресурсов для обработки и снижают производительность.

Любое поле, в котором должны быть только отличные от нуля значения, нужно объявлять как NOT NULL

Для любого поля, которое должно содержать уникальные значения, стоит указать модификатор UNIQUE

Хранение изображений в БД нежелательно. Храните в таблице путь к файлу (локальный путь или URL), а сам файл помещайте в файловую систему сервера. 

Рекурсивный алгоритм[править]

Для того, чтобы обеспечить время при памяти , определим матрицу минимальных расстояний между суффиксами строк, то есть — расстояние между последними символами и последними символами . Очевидно, матрицу можно вычислить аналогично матрице , и так же быстро.

Теперь опишем алгоритм, считая, что  — кратчайшая из двух строк.

• Если длина одной из строк (или обеих) не больше , задача тривиальна. Если нет, выполним следующие шаги.
• Разделим строку на две подстроки длиной . (Если нечётно, то длины подстрок будут и .) Обозначим подстроки и .
• Для вычислим последнюю строку матрицы для строк и , последнюю строку матрицы для строк и .
• Найдём такое, что минимально. Здесь и  — матрицы из предыдущего шага, но мы используем только их последние строки. Таким образом, мы нашли разбиение на две подстроки, минимизирующее сумму расстояния левой половины до левой части и расстояния правой половины до правой части . Следовательно, левая подстрока соответствует левой половине , а правая — правой.
• Рекурсивно ищем редакционное предписание, превращающее в левую часть (то есть в подстроку )
• Рекурсивно ищем редакционное предписание, превращающее в правую часть (то есть в подстроку ).
• Объединяем оба редакционных предписания.

Псевдокодправить

int levensteinInstruction(String s1, String s2):
   if  s1.length <=  1 || s2.length <= 1  
       Решаем тривиально, возвращаем редакционное предписание
   else    
       String s1l, s1r, s2l, s2r
       if  s2.length < s1.length 
           s1l = s1.substring(0, s1.length / 2)            
           s1r = s1.substring(s1.length / 2, s1.length)   
                                                          
           d = calcD(s1l, s2)                             
           e = calcE(s1r, s2)                             
           k = 0
           for i = 1 to s2.length
               if d + e < d + e
                   k = i
           s2l = s2.substring(0, k)
           s2r = s2.substring(k, s2.length)
       else
                                                          
           s2l = s2.substring(0, s2.length / 2)           
           s2r = s2.substring(s2.length / 2, s2.length)   
           d = calcD(s2l, s1)                             
           e = calcE(s2r, s1)                             
           k = 0
           for i = 1 to s1.length
               if d + e < d + e
                   k = i
           s1l = s1.substring(0, k)
           s1r = s1.substring(k, s1.length)
   return levensteinInstruction(s1l, s2l) + levensteinInstruction(s1r, s2r)

Время выполнения удовлетворяет (с точностью до умножения на константу) условию

,

Докажем:

База индукции очевидна

Пусть для всех выполнено .
Тогда учитывая , , получим:

следовательно

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

Т.к. мы вычисляем функцию рекурсивно, требуемый размер стека тоже следует учесть. На стек вызовов потребуется памяти, потому общая оценка использования памяти будет

И снова о скорости работы 1с 8.х + тест от Гилева (конфигурация TPС_1C_GILV_A) + как Выбрать сервер для 1С 8.х Промо

Предыстория:
Есть в конторе, где я работаю, пара практически ОДИНАКОВЫХ по железу сервера…
так вот заметили что на одном из них 1С 8.2 работает значительно быстрей что в Клиент-Серверном, что в файловом варианте…
и что именно удивило так это что медленней работал сервер с большим количеством Оперативной памяти + RAID10 на SSD.
Проводили много тестов на работу дисковой системы + различные тесты SQL — ВЫВОД: ничего непонятно где тормоза.
И вот попала ко мне конфигурация 1С для оценки производительности 1С от Гилева http://infostart.ru/public/57204/
Подробности в Описании…

2 стартмани

C#[править]

public static int LevenshteinDistance(string string1, string string2)
{
    if (string1 == null) throw new ArgumentNullException("string1");
    if (string2 == null) throw new ArgumentNullException("string2");
    int diff;
    int m = new intstring1.Length + 1, string2.Length + 1];

    for (int i = ; i <= string1.Length; i++) { mi,  = i; }
    for (int j = ; j <= string2.Length; j++) { m, j = j; }

    for (int i = 1; i <= string1.Length; i++)
    {
        for (int j = 1; j <= string2.Length; j++)
        {
            diff = (string1i - 1 == string2j - 1]) ?   1;

            mi, j = Math.Min(Math.Min(mi - 1, j + 1, mi, j - 1 + 1), mi - 1, j - 1 + diff);
        }
    }
    return mstring1.Length, string2.Length];
}

Пример использования:

string s1="мама";
string s2="папа";
int diff=LevenshteinDistance(s1,s2);

Алгоритм Вагнера — Фишера[править]

Для нахождения кратчайшего расстояния необходимо вычислить матрицу , используя . Её можно вычислять как по строкам, так и по столбцам

Псевдокод алгоритма, написанный при произвольных ценах замен, вставок и удалений (важно помнить, что элементы нумеруются с ):

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

int levensteinInstruction(String s1, String s2, int InsertCost, int DeleteCost, int ReplaceCost):
  D = 0
  for j = 1 to N
    D = D + InsertCost                  
  for i = 1 to M
    D = D + DeleteCost                  
    for j = 1 to N
      if S1 != S2 
         D = min(D + DeleteCost,        
                       D + InsertCost,                      
                       D + ReplaceCost)                 
      else 
         D = D
  return D

Памятьправить

Алгоритм в виде, описанном выше, требует операций и такую же память, однако, если требуется только расстояние, легко уменьшить требуемую память до . Заметим, что для вычисления нам нужно только , поэтому будем вычислять в , а в . Осталось только поменять местами и .

int levensteinInstruction(int[] D):
  for i = 0 to M
    for j = 0 to N
      вычислить D
    swap(D, D)
  return D

Go[править]

func distance(s1, s2 string) int {
	min := func(values ...int) int {
		m := values
		for _, v := range values {
			if v < m {
				m = v
			}
		}
		return m
	}
	r1, r2 := []rune(s1), []rune(s2)	
	n, m := len(r1), len(r2)
	if n > m {
		r1, r2 = r2, r1
		n, m = m, n
	}
	currentRow := make([]int, n+1)
	previousRow := make([]int, n+1)
	for i := range currentRow {
		currentRowi = i
	}
	for i := 1; i <= m; i++ {
		for j := range currentRow {
			previousRowj = currentRowj
			if j ==  {
				currentRowj = i
				continue
			} else {
				currentRowj = 
			}
			add, del, change := previousRowj+1, currentRowj-1+1, previousRowj-1
			if r1j-1 != r2i-1 {
				change++
			}
			currentRowj = min(add, del, change)
		}
	}
	return currentRown
}

Магазин Froot

Это маркетплейс, где один товар могут продавать десяток продавцов, выставляя разную стоимость. Подробнее о проектах Froot в портфолио rocketfirm.com.

Товар в базу данных магазина продавец передает через XML или через API. Продавец указывает, как называется товар, сколько его штук и сколько он стоит — все из его базы данных товаров. С количеством и стоимостью товара никаких проблем нет — бери себе, складывай в соответствующие ячейки SQL и выводи после на сайте. Проблема появилась с названиями.

Чаще всего продавец уже продает товары через свой сервис — то есть, у него есть своя система названий товаров, которую он под нас менять не будет (это время, деньги и лень). Имеем проблему: товар под названием “iPhone X серый 256 гигабайт” и “iPhone X 256 Gray”, попав в нашу базу, не найдут друг друга и станут двумя разными товарами. Если таких продавцов 10, и у каждого свое название (не говоря об ошибках в названиях), это не сделает хорошо ни нам, ни покупателям.

В многих маркетах эту проблему решают просто: сидит специально обученный человек и совмещает это все руками. Пришел к нему “iPhone X Grey 256 retina”, он его заботливо добавляет к “iPhone X 256Gb Gray”. У клиента таких ресурсов не оказалось, но подвернулся интересный инструмент — расстояние Левенштейна.

PHP[править]

<?PHP

function distance($source, $dest) {
    if ($source == $dest) {
        return ;
    }

    list($slen, $dlen) = strlen($source), strlen($dest)];

    if ($slen ==  || $dlen == ) {
        return $dlen ? $dlen  $slen;
    }

    $dist = range(, $dlen);

    for ($i = ; $i < $slen; $i++) {
        $_dist = $i + 1];
        for ($j = ; $j < $dlen; $j++) {
            $cost = ($source$i == $dest$j]) ?   1;
            $_dist$j + 1 = min(
                $dist$j + 1 + 1,   // deletion
                $_dist$j + 1,      // insertion
                $dist$j + $cost    // substitution
            );
        }
        $dist = $_dist;
    }

    return $dist$dlen];
}

$source = 'PHP';
$dest = 'new PHP test';

echo distance($source, $dest) . "\n";
echo levenshtein($source, $dest); // built-in PHP function
?>

Советы по оптимизации хранимых процедур и SQL пакетов

Инкапсулируйте ваш код в хранимых процедурах

Для обработки данных используйте хранимые SQL процедуры.

Когда хранимая процедура выполняется в первый раз (и у нее не определена опция WITH RECOMPILE), она оптимизируется, для нее создается план выполнения запроса, который кешируется SQL сервером. Если та же самая хранимая процедура вызывается снова, она будет использовать кешированный план выполнения запроса, что экономит время и увеличивает производительность. 

Всегда включайте в ваши хранимые процедуры инструкцию «SET NOCOUNT ON». Если Вы не включите эту инструкцию, тогда каждый раз при выполнении запроса SQL сервер отправит ответ клиенту, указывающему число строк, на которые воздействует запрос.

Избегайте использования курсоров

По возможности выбирайте быстрый forward-only курсор

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

Когда Вы закончили использовать курсор, как можно раньше не только ЗАКРОЙТЕ (CLOSE) его, но и ОСВОБОДИТЕ (DEALLOCATE).

Используйте триггеры c осторожностью

Триггеры — это усложнение логики работы приложения, неявное неожиданное выполнение дополнительных действий. 

Триггеры усложняют интерфейс хранимых процедур. Поместите все необходимые проверки и действия в рамки хранимых процедур. 

Временные таблицы для больших таблиц, табличные переменные — для малых (меньше 1000)

Если вам требуется хранить промежуточные данные в таблицах, то используйте табличные переменные (@t1) для малых таблиц, а временные таблицы (#t1) — для больших. 

Подробнее: 

При определении временной таблицы имеет смысл проверить ее на существование: 

Также для улучшения быстродействия используйте для временной таблицы первичный ключ и индексы.