СПОСОБЫ И СИСТЕМЫ ДЛЯ РЕАЛИЗАЦИИ ПРИБЛИЖЕННОГО СРАВНЕНИЯ СТРОК В БАЗЕ ДАННЫХ

1. Компьютерный способ сравнения символьных строк, символьной строки кандидата с множеством записей символьных строк, сохраненных в базе данных, упомянутый способ включает:
a) идентификацию набора ссылочных символьных строк в базе данных, ссылочные символьные строки идентифицируются с использованием оптимизированного поиска набора разнородных символьных строк;
b) генерирование представления n-граммы одной из ссылочных символьных строк в наборе ссылочных символьных строк;
c) генерирование представления n-граммы символьной строки кандидата;
d) определение подобия между представлениями n-грамм;
e) повторение шагов b) и d) для оставшихся ссылочных символьных строк в наборе идентифицированных ссылочных символьных строк; и
f) индексацию символьной строки кандидата в базе данных, основанную на определении релевантности между представлением n-граммы символьной строки кандидата и ссылочными символьными строками в идентифицированном наборе.
2. Компьютерный способ по п.1, отличающийся тем, что определение подобия между представлениями n-граммы включает:
вычисления двумерного вектора, содержащего частоту возникновения всех уникальных n-грамм в символьной строке кандидата и частоту возникновения всех уникальных n-грамм в ссылочной символьной строке; и
вычисление метрики подобия для символьной строки кандидата, относительно ссылочной символьной строки, основанной на двумерном векторе.
3. Компьютерный способ по п.2, отличающийся тем, что вычисление метрики подобия для символьной строки кандидата включает использование вычисления структурированного языка запроса для сравнения содержания двумерного вектора.
4. Компьютерный способ по п.2, отличающийся тем, что вычисление метрики подобия включает:
определение величины вектора, ассоциированного с символьной строкой кандидата, как величины А;
определение величины вектора, ассоциированного со ссылочной символьной строкой, как величины В;
вычисление скалярного произведения между этими двумя векторами; и
вычисление метрики подобия согласно (скалярное произведение/(Величина А × Вличина В)).
5. Компьютерный способ по п.2, отличающийся тем, что вычисление метрики подобия включает реализацию вычисления n-грамм частоты подобия в ASCII структурированного языка запроса.
6. Компьютерный способ по п.5, отличающийся тем, что дополнительно включает использование вычисление n-грамм частоты подобия для формирования двоичного ключа, который указывает на подобие между символьной строкой кандидата и каждой из идентифицированных ссылочных символьных строк.
7. Компьютерный способ по п.2, отличающийся тем, что индексирование символьной строки кандидата в базе данных включает:
реализацию вычисления n-грамм частоты подобия;
использование вычисления для формирования двоичных ключей, которые указывают на подобие между записью, связанной с символьной строкой кандидата, и записью, связанной с каждой из идентифицированных ссылочных символьных строк;
присоединение записей, которые совместно используют то же значение двоичного ключа; и сортировку присоединенных записей по релевантности суммированием весовых коэффициентов частоты всех сравниваемых n-грамм.
8. Компьютерный способ по п.1, отличающийся тем, что индексация символьной строки кандидата включает генерирование матрицы метрик подобия для символьной строки кандидата по сравнению с набором ссылочных символьных строк.
9. Компьютерный способ по п.1, отличающийся тем, что индексация символьной строки кандидата включает:
присвоение двоичному ключу соответствующего ссылочной символьной строке значения 1, если метрика подобия выше предопределенного порога; и
присвоение двоичному ключу соответствующего ссылочной символьной строке значение 0, если метрика подобия ниже предопределенного порога.
10. Компьютерный способ по п.1, отличающийся тем, что идентификация набора ссылочных символьных строк в базе данных включает использование основного компонентного фактора анализа для идентификации набора разнородных записей символьных строк.
11. Компьютер, программированный для:
использования оптимизированного поиска для идентификации набора разнородных ссылочных символьных строк в базе данных;
генерирования представления n-граммы для символьной строки кандидата;
генерирования представления n-граммы для каждой из разнородных ссылочных символьных строк в наборе;
определения подобия между представлением n-граммы символьной строки кандидата и каждым представлением n-граммы набора разнородных ссылочных символьных строк; и индексирования символьной строки кандидата в базе данных, основанной на общих символах, определенных в представлениях n-граммы.
12. Компьютер по п.11, отличающийся тем, что для определения подобия между представлением n-граммы символьной строки кандидата и каждым представлением n-граммы набора разнородных ссылочных символьных строк упомянутый компьютер дополнительно программируется для
вычисления двумерных векторов, содержащих частоту возникновения всех уникальных n-грамм в символьной строке кандидата и всех уникальных n-грамм в одной из ссылочных символьных строк для каждой из ссылочных символьных строк; и
вычисление метрики подобия для символьной строки кандидата относительно каждой ссылочной символьной строки, основанной на двумерных векторах.
13. Компьютер по п.12, отличающийся тем, что для вычисления метрики подобия упомянутый компьютер программируется, чтобы использовать вычисления структурированного языка запроса, чтобы сравнить содержание двумерных векторов.
14. Компьютер по п.11, отличающийся тем, что для индексирования символьной строки кандидата упомянутый компьютер программируется для:
присвоения двоичному ключу соответствующей ссылочной символьной строки значение 1, если определено, что подобие выше предопределенного порога; и
присвоения двоичному ключу соответствующей ссылочной символьной строки значения 0, если определено, что подобие ниже предопределенного порога.
15. Компьютер по п.11, отличающийся тем, что для проведения оптимизированного поиска упомянутый компьютер программируется, чтобы использовать основной компонентный фактор анализа для идентификации набора разнородных ссылочных символьных строк в базе данных.
16. Компьютерный способ для приблизительного сравнения символьной строки кандидата с набором ссылочных символьных строк в базе данных, упомянутый способ включает:
отдельное сравнение представления n-граммы символьной строки кандидата с представлениями n-граммы каждой ссылочной символьной строки в наборе ссылочных символьных строк; и
генерирование двоичного индексного значения, которое ассоциируется с символьной строкой кандидата, причем двоичное индексное значение указывает на подобие между символьной строкой кандидата и каждой из ссылочных символьных строк.
17. Компьютерный способ по п.16, отличающийся тем, что отдельное сравнение представления n-граммы символьной строки кандидата с представлениями n-граммы каждой ссылочной символьной строки включает использование вычисления подобия частоты n-граммы на структурированном языке запросов для сравнения представленных n-грамм.
18. Компьютерный способ по п.16, отличающийся тем, что отдельное сравнение представления n-граммы символьной строки кандидата с представлениями n-граммы каждой ссылочной символьной строки включает:
a) определение величины (А) вектора, ассоциированного с представлением n-граммы символьной строки кандидата;
b) определение величины (В) вектора, ассоциированного с представлением n-граммы одной из ссылочных символьных строк как величины В;
c) вычисление скалярного произведения между этими двумя векторами; и
d) вычисление метрики подобия символьной строки кандидата относительно ссылочной символьной строки согласно (скалярное произведение/(величина А × величина В)); и повторение шагов b), с) и d) для каждой ссылочной символьной строки.
19. Компьютерный способ по п.16, отличающийся тем, что символьная строка кандидата - одно из торговых названий и торговых адресов, а набор ссылочных символьных строк в базе данных - соответственно, больший набор торговых названий и торговых адресов.
20. Компьютерный способ по п.16, отличающийся тем, что дополнительно включает
присоединение записей, которые совместно используют одно двоичное индексное значение; и
сортировку присоединенных записей по релевантности суммированием результатов представления частотных весовых коэффициентов всех сравниваемых n-грамм.