Постараюсь объяснить, что требуется. Это нечто на подобие нейросети.
Представит базу данных с 1 млн строк, каждая строка это набор слов(например):
1. собака кот стул дерево свинья пушка
2. ложка кран кот суп
Количество слов(в каждой строке) большое(например до 100 слов), в каждой строке разное количество слов.
Далее на вход подается строка(набор слов). Задача: найти строки(из базы данных), которые максимально совпадают с заданной строкой. Предположим на 97% совпало со строкой №717392, также на 95% совпало со строкой №1811 и тд.
Сама база данных еще не создана, мне предстоит создать её такой что бы по ней было максимально эффективно искать совпадения.
Как это все лучше реализовать? И желательно что бы шустро работало, так как например поисковик Гугл(если вставить цитату из книги он сразу находит на каком-то сайте её текст).
C/C++
Как реализовать поиск похожей строки в базе данных?
Критерий релевантности не определён. Сравниваемые строки могут быть разных размеров!! Слова в сравниваемых строках могут совпадать по значению, но не совпадать по позиции в тексте. Как быть со знаками препинания и регистром символов? Что делать если в сравниваемых строках слова с одинаковым значением встречаются несколько раз и их количество не совпадает? Как поступать с орфографическими ошибками? (задание с звёздочкой)
А вообще-то, надо делать словарь, так как у вас 1.000.000 строк по 100 слов – это максимум 100.000.000 слов, а следовательно они будут повторятся, поэтому проще будет хранить таблицу строк из целочисленных ключей, ссылающихся на таблицу слов по уникальному ключу. Грузить данные придётся частями в несколько запросов, выполняемых в параллельных потоках. Запросы выполнять с использованием хранимых процедур (так быстрее). Выборку делать по принципу поиска абсолютных несовпадений с последующим их исключением (так как чаще строки будут абсолютно не совпадать). Полученные таким образом данные хранить в структурах с полями: int id – номер строки, float q – коэффициент совпадения (0.0 < q <= 1.0), умножив который на 100 получите значение в процентах. Отсортировав вектор структур по коэффициентам от большего к меньшему получите результат, при котором вначале вектора будут лучшие варианты совпадений. Для простоты сортировки в структуре перегрузите operator< и operator>
А вообще-то, надо делать словарь, так как у вас 1.000.000 строк по 100 слов – это максимум 100.000.000 слов, а следовательно они будут повторятся, поэтому проще будет хранить таблицу строк из целочисленных ключей, ссылающихся на таблицу слов по уникальному ключу. Грузить данные придётся частями в несколько запросов, выполняемых в параллельных потоках. Запросы выполнять с использованием хранимых процедур (так быстрее). Выборку делать по принципу поиска абсолютных несовпадений с последующим их исключением (так как чаще строки будут абсолютно не совпадать). Полученные таким образом данные хранить в структурах с полями: int id – номер строки, float q – коэффициент совпадения (0.0 < q <= 1.0), умножив который на 100 получите значение в процентах. Отсортировав вектор структур по коэффициентам от большего к меньшему получите результат, при котором вначале вектора будут лучшие варианты совпадений. Для простоты сортировки в структуре перегрузите operator< и operator>
>Как это все лучше реализовать?
При помощи имеющихся в твоей СУБД встроенных функций оценки совпадений строк. Поскольку СУБД ты заботливо не указал, ничего более конкретного сказать невозможно.
Хочу только заметить, что на данные функции не действуют никакие индексы и все прочие ухищрения, тебе придется сравнить каждую строку с каждой. То есть если у тебя там миллион строк, придется сделать полтриллиона сравнений. И вернется полтриллиона строк с проставленными оценками совпадений.
Ну а гугель работает путем индексации слов и всяких хитромудрых их оценок важности и всего прочего. В твоем случае так оно не сработает, иначе придется написать собственный гугель.
При помощи имеющихся в твоей СУБД встроенных функций оценки совпадений строк. Поскольку СУБД ты заботливо не указал, ничего более конкретного сказать невозможно.
Хочу только заметить, что на данные функции не действуют никакие индексы и все прочие ухищрения, тебе придется сравнить каждую строку с каждой. То есть если у тебя там миллион строк, придется сделать полтриллиона сравнений. И вернется полтриллиона строк с проставленными оценками совпадений.
Ну а гугель работает путем индексации слов и всяких хитромудрых их оценок важности и всего прочего. В твоем случае так оно не сработает, иначе придется написать собственный гугель.
Максим Боян
50 396
Вариант: Postgresql - pg_trgm
Алексей Сурков
73 814
"которые максимально совпадают с заданной строкой. "
А где у тебя четкое определение величины совпадения?
Такое, как у гугги у тебя никогда не будет.
Более того, из тебя врядл ли выйдет приемлемый прогер.
А где у тебя четкое определение величины совпадения?
Такое, как у гугги у тебя никогда не будет.
Более того, из тебя врядл ли выйдет приемлемый прогер.
Аслан Куракбаев
11 711
Похожие вопросы
- Переход на следующую строку при считывании данных из файла в Си
- Как реализовать поиск наибольшего значения в одномерном массиве при помощи циклов.
- Найти максимальный элементы в строке матрицы
- Работа со строками, поиск слова
- Программирование на С++ (строки)
- Двумерный динамический массив с неизвестны количеством столбиков или строк
- Передача строк в функцию С++
- Синтаксическая ошибка: константа строки в с++
- C++: "С-Строка" и ошибка
- С++. Упорядочить строки массива A в порядке убывания сумм цифр первого элемента каждой строки.
Думаете у них стоят супер-мощные сервера, которые сравнивают каждое лицо(его биометрические данные) со всей БД? И это ж много пользователей параллельно ищут.
Мне не надо такое создавать, честно, но мое очень похожее по принципу. надо реально сравнить строку(как набор этих биометрических данных лица) с БД этих строк(типо лиц).
Вот если этот findface, как бы вы сказали он работает?