Каков лучший способ нечеткого сравнения двух таблиц
У меня есть две таблицы с ~ 70 000 строк. Обе таблицы имеют столбец «заголовок». Мне нужно сравнить таблицы и найти их пересечения по заголовку столбца. Я пытаюсь использовать JOIN и UNION, но названия могут немного отличаться. Я имею в виду, в одной таблице это может быть Нью-Йорк, США но в других это может быть Нью-Йорк, США. Я гуглил это, и это вызывает «поиск нечеткой строки».
Я уже начинаю с php и Similar_text, но это очень медленно … Я думаю, что для этой задачи я должен использовать что-то еще, как р возможно .. Я уже помещаю эти данные в BigQuery, но BigQuery поддерживает только REGEXEP для поиска в выражении where, или я не могу понять, как его следует использовать.
Может ли R решить мои проблемы со скоростью?
Спасибо!
Пример dataset1:
new-york, usa|100|5000
dataset2:
newyork usa|50|1000
nnNew-York |10|500
Пример желаемого результата:
New-York, Usa|160|6500
Другими словами, мне нужно создать новую таблицу, которая будет содержать данные из обеих таблиц.
ОБНОВЛЕНО
Спасибо за ваши ответы, я попробовал R и agrep, он работает, но очень медленно. 2 000 строк за 40 минут, у меня всего 190 000 строк. Это нормально?
Решение
Это слишком долго для комментария.
Ответ на ваш вопрос — «Расстояние Левенштейна». Однако при 70000 строк это требует примерно 70 000 * 70 000 сравнений — 490 миллионов. Это много.
Выполнение работы в R может быть вашим лучшим подходом, потому что R будет хранить все данные в памяти и, вероятно, будет более эффективным, чем реализация в MySQL.
Есть способы замкнуть поиск. Один из методов, например, состоит в том, чтобы разделить каждую строку на n-граммы (триграммы типичны) и использовать их для сокращения пространства поиска. В конце концов, у «Нью-Йорка» и «Далласа» нет общих букв, поэтому на самом деле не нужно сравнивать.
Вероятно, в R есть подпрограммы для обработки триграмм. Их довольно легко сделать в MySQL, но они не встроены.
Другие решения
Других решений пока нет …