Нечеткое совпадение имени с 5 миллионами имен и создание списка возможных совпадений
Мне нужно сопоставить имя конкретного человека с большим списком (>5 миллионов) имен, используя нечеткое сопоставление (насколько близко оно совпадает).
Один из подходов заключается в использовании расстояния редактирования между входом и каждым именем в списке. выберите имена, которые имеют меньшее редактируемое расстояние (скажем, меньше 4) в качестве попадания. Проблема в том, что он линейный и медленный.
Я хочу, чтобы это сопоставление было выполнено за < 1 миллисекунд. Это означает, что данные должны быть запоминающимися и параллельными.
Я немного читал, и мне нужно выбрать подмножество, которое может иметь возможное совпадение, а затем запустить логику редактирования расстояния. триграммы предлагаются. Кажется, что Postgress SQL использует триграмму для нечеткого соответствия.
что мне не ясно, так это то, как использовать триграмму для подбора меньшего подмножества, которое, вероятно, будет совпадать.
Хотите знать, если кто-то сталкивался с подобной проблемой, и если да, пожалуйста, поделитесь своими мыслями. Также полезен любой указатель библиотеки / инструмента с открытым исходным кодом.
Спасибо
Вот некоторые ссылки, которые я нашел для сопоставления логики.