Быстрый способ поиска на основе небуквального сравнения
Я разрабатываю небольшой поиск по довольно большим наборам данных, в основном по всем строкам. Отношения между полями таблицы достаточно просты, хотя сравнение не должно быть буквальным. т. е. он должен уметь соотносить «filippo», «philippo», «filippo» и т. д.
Я нашел несколько способов сделать это, очень часто натыкаясь на расстояние Левинштейна (это, здесь и здесь), хотя я не уверен, что это практично в моем конкретном случае.
В двух словах у меня есть две таблицы, маленькая с «ключами поиска» и более массивная, в которой должен выполняться поиск. Обе таблицы имеют одинаковые поля и одинаковое «значение». Например.
KEYS_TABLE
# | NAME | MIDNAME | SURNAME | ADDRESS | PHONE
1 | John | Fake | Doe | Sesame St. | 333-12-32
2 | Ralph | Stue | Michel | Bart. Ghost St. | 778-13000
...
и
SEARCH_TABLE
# | NAME | MIDNAME | SURNAME | ADDRESS | PHONE
...
532 | Jhon | F. | Doe | Sesame Street | 3331232
...
999 | Richard | Dalas | Doe | Sesame St. | 333-12-32
Все, что я хочу сделать, это получить какую-то метрику или ранг для каждой данной записи в KEYS_TABLE
, сообщить обо всех записях из SEARCH_TABLE
выше определенной релевантности (определяемой либо метрикой, либо просто каким-либо методом, подобным «KNN»).
Я говорю, что расстояние Левинштейна может оказаться нецелесообразным, потому что потребуется вычислять каждое поле в каждой строке в KEYS_TABLE
x SEARCH_TABLE
. Учитывая, что SEARCH_TABLE
имеет около 400 миллионов записей, а KEYS_TABLE
варьируется от 100k до 1mil, результирующее число слишком велико.
Я надеялся, что есть какой-то способ, которым я мог бы предварительно обогатить обе таблицы, или какой-то более простой (дешевый) способ выполнить поиск.
Стоит отметить, что мне разрешено преобразовывать данные по желанию. например нормализовать St.
до st
, Street
до st
, удалить специальные символы и так далее.
Какие у меня будут варианты?