В первом посте по этой теме мы рассмотрели, как построить серию определяемых пользователем функций (UDF) для реализации алгоритма Soundex. Напомним, идея состоит в том, чтобы создать набор инструментов, который можно использовать для решения проблем, связанных с нечетким сопоставлением и управлением основными данными. Теперь Soundex - первое, что у нас есть!
С тех пор, как я написал этот пост, меня завалили электронными письмами, в которых спрашивали о его производительности. Одно из преимуществ Soundex заключается в том, что он работает довольно быстро. Когда вы добавляете в BigQuery возможности массовой параллельной обработки, вы получаете не очень тяжелый Soundex.
Должен Soundex быстрее
Раньше мы использовали несколько имен для выборочной проверки самого алгоритма. Давайте добавим в этот список еще несколько имен и посмотрим, что из этого получится. Поехали, чтобы получить данные!
Поиск некоторых данных по именам привел меня к веб-сайту генеалогических данных Бюро переписи населения США. Список часто встречающихся фамилий был составлен по результатам двух последних переписей (2010 и 2000 гг.). Перепись 1990 года дала нам имена и фамилии мужчин и женщин. Я взял все опубликованные данные для публичного использования и бросил их в таблицу BigQuery. В целом, нам удалось собрать почти 400 000 фамилий, чтобы запустить наши запросы.
Теперь некоторые из них будут повторяться, поэтому практическая применимость самих алгоритмов нечеткого сопоставления немного ограничена. Но здесь мы пытаемся увидеть, насколько быстро это происходит. 400 000 - это немного больше, чем 20. Если на секунду надеть на себя локальную программную интеграцию данных / качество данных, я бы обычно ожидал, что это займет час, может быть? Десятки минут? Но это же BigQuery, так что хоть несколько минут?
Пять секунд - это довольно быстро при обработке почти полумиллиона имен. Удвоение количества имен до миллиона не оказало большого влияния на общее время обработки.
Дело в том, что увеличение времени обработки в результате удвоения размера и без того довольно большого списка имен настолько номинально, что вполне возможно, что это просто связано с прогревом вычислений, а не с увеличением обрабатываемых данных. Идея использования мощности базы данных для выполнения подобных операций не нова, но возможность получить эти результаты так быстро с нулевой инфраструктурой и без инструментов - это довольно круто, если я сам так говорю.
Кроме того, если вы хотите запустить их самостоятельно, я сделал объединенные данные переписи в единую таблицу, доступную как экспорт CSV.
Теперь, когда у нас есть базовая фонетическая классификация, что дальше? У нас должно быть хорошо, правда? Не совсем так. Давайте поговорим о создании еще одного инструмента для нашего набора инструментов.
Представляем Владимира Левенштейна
Владимир Левенштейн был российским ученым, специализирующимся, в том числе, на теории информации. Это форма метрики расстояния, называемая расстояние редактирования, которая на высоком уровне представляет собой сравнение количества изменений, необходимых для превращения одной строки в другую. Расстояние Левенштейна было создано в 1965 году и является мерой того, сколько вставок, замен и удалений происходит от одной строки к другой. Вот несколько действующих примеров:
- «Виски» - «Виски»: расстояние Левенштейна, 1. Добавляется буква «е».
- «Drinjs» - «Напитки»: Левенштейн Расстояние: 1. Буква «k» заменяется на «j».
- « Чендлер Бинг - Мисс Чанандлер Бонг »: Расстояние Левенштейна, 8. Добавить Мисс (5), добавить an (2), заменить i на o (1).
Имейте в виду, что это базовый алгоритм, который придает одинаковый вес вставкам, заменам и удалениям. Есть варианты по этому поводу, которые придают разный вес различным операциям, что вы можете делать в зависимости от вашего варианта использования (например, в вариантах использования OCR вы можете присвоить меньший вес 'l' / '1' и ' O '/' 0 'замен). Если вам интересно, как работает алгоритм, есть отличный Средний пост, который проведет вас через матричные операции, чтобы получить правильное расстояние. Это определенно стоит прочитать! Когда алгоритм обрабатывает две строки, результат вычисления представляет собой число, которое дает чистое количество изменений.
Итак, как нам заставить это работать? Еще один UDF! В функции Soundex мы смогли связать вместе серию операторов SQL, но теперь мы ищем циклы, поэтому нам придется использовать некоторый JavaScript. Если вы не любите читать подробное объяснение, связанное ранее, люди из Университета Питтсбурга свели его к следующим шагам:
1 - Установите n равным длине s. Установите m равным длине t .
Если n = 0, вернуть m и выйти.
Если m = 0, вернуть n и exit.
Создайте матрицу, содержащую 0..m строк и 0..n столбцов.
2 - Инициализировать первую строку значением 0..n.
Инициализировать первый столбец значением 0..m.
3 - Изучите каждый символ s (i от 1 до n).
4 - Изучите каждый символ t (j от 1 до m).
5 - Если s [i] равно t [j], стоимость равна 0. Если s [i] не равно t [j], стоимость равна 1.
6 - Установите ячейку d [i, j] матрицы равной минимуму:
а. Ячейка непосредственно выше плюс 1: d [i-1, j] + 1.
b. Ячейка слева от плюс 1: d [i, j-1] + 1.
c. Ячейка по диагонали выше и слева плюс стоимость: d [i-1, j-1] + стоимость.
7 - После завершения шагов итерации (3, 4, 5, 6) расстояние находится в ячейке d [n, m].
Предыдущая ссылка, объясняющая, как работает алгоритм, также содержит пошаговые иллюстрации матриц, демонстрирующие, как он выполняет итерацию по данным, и в Интернете также доступен код, в котором этот алгоритм реализован на JavaScript. Поскольку он распространяется под лицензией MIT OSI, давайте поместим его в BigQuery UDF!
CREATE OR REPLACE FUNCTION
dq.dq_fm_LevenshteinDistance(in_a string,
in_b string)
RETURNS INT64
LANGUAGE js AS
"""/*
* Data Quality Function - Fuzzy Matching
* dq_fm_LevenshteinDistance
* Based off of https://gist.github.com/andrei-m/982927
* input: Two strings to compare the edit distance of.
* returns: Integer of the edit distance.
*/
var a = in_a.toLowerCase();
var b = in_b.toLowerCase();
if(a.length == 0) return b.length;
if(b.length == 0) return a.length;
var matrix = [];
// increment along the first column of each row
var i;
for(i = 0; i <= b.length; i++){
matrix[i] = [i];
}
// increment each column in the first row
var j;
for(j = 0; j <= a.length; j++){
matrix[0][j] = j;
}
// Fill in the rest of the matrix
for(i = 1; i <= b.length; i++){
for(j = 1; j <= a.length; j++){
if(b.charAt(i-1) == a.charAt(j-1)){
matrix[i][j] = matrix[i-1][j-1];
} else {
matrix[i][j] =
Math.min(matrix[i-1][j-1] + 1, // substitution
Math.min(matrix[i][j-1] + 1, // insertion
matrix[i-1][j] + 1)); // deletion
}
}
}
return matrix[b.length][a.length];
"""
Давай закружим!
WITH
data AS (
SELECT
'Whiskey' a,
'whisky' b
UNION ALL
SELECT
'drinjs' a,
'Drinks' b
UNION ALL
SELECT
'Chandler Bing' a,
'Miss Chanandler Bong' b)
SELECT
a,
b,
`dq.dq_fm_LevenshteinDistance`(a, b) as ldistance
FROM
data
Итак, давайте сделаем несколько вещей, чтобы увидеть, как эти двое работают вместе.
Лучше вместе!
С помощью Soundex мы, по сути, добавляем метаданные к существующему элементу данных, так что это довольно просто. С расстоянием редактирования мы делаем одно за другим сравнения. Сравнение всех 380 000 имен из нашего исходного набора данных со всеми 379 999 (ish) именами в нашем новом наборе данных будет значительно большим количеством сравнений, чем мы хотим или должны делать. Вот где объединение Soundex с расстояниями редактирования немного упрощает работу. Взяв каждый элемент и сравнив расстояние редактирования со всеми другими элементами в одном и том же коде Soundex, вы значительно сократите количество сравнений, которые необходимо провести. Это может выглядеть примерно так:
WITH
# Create base table of last names with Soundex codes
name_data AS (
SELECT
lname,
`dq.dq_fm_Soundex`(lname) soundex_code
FROM
`dq.name_data`
WHERE
lname IS NOT NULL),
# Create table that's joined with itself on the Soundex code
joined_data AS (
SELECT
p.lname AS p_lname,
c.lname c_lname,
p.soundex_code
FROM
name_data p,
name_data c
WHERE
p.soundex_code = c.soundex_code
AND p.lname != c.lname)
# Apply Levenshtein Distance to each pair
SELECT
*,
`dq.dq_fm_LevenshteinDistance`(p_lname, c_lname) AS ldistance
FROM
joined_data
ORDER BY
soundex_code,
p_lname ASC
Похоже, это сработало! Я хотел бы отметить несколько моментов в деталях выполнения запроса.
Во-первых, количество строк, созданных на этапе Join +. Это говорит нам о том, что нам нужно было выполнить вычисления для 111 миллионов строк из набора данных, содержащего все сравнения, которые нужно было сделать. Сказав это, следующее, что я хотел бы отметить, - это прошедшее время. 8 минут 43 секунды. Довольно быстро, если вы спросите меня.
Теперь давайте посмотрим на вкладку "Информация о вакансии".
Вот метрики ценообразования по запросу для BigQuery для справки.
Возвращаясь к данным, давайте сохраним результаты предыдущего запроса в другую таблицу, чтобы нам было проще использовать! Мы рассмотрим пример кода Soundex и посмотрим, как он выглядит. Выберите «Различный», чтобы исключить дубликаты из-за совпадения «общих названий» за годы переписи.
Просматривая здесь полученные данные, мы видим, что они получают результаты для всех возможных значений ldistance. Как показано здесь, он забрасывает слишком широкую сеть и не очень полезен. Например, совершенно очевидно, что «Гарси» и «Гроховски» - это не одно и то же. Давайте настроим это немного, посмотрев на элементы с расстоянием Левенштейна менее четырех.
Вы сразу заметите, что, уменьшая диапазон редактируемого расстояния, вы начинаете получать более близкие друг к другу объекты. Сужая диапазон сравнений до групп, которые соответствуют фонетически, мы также улучшаем производительность. Пример с «Георгиу» показывает результаты, которые больше похожи на те же самые.
Опять же, это не полный метод нечеткого сопоставления, но он показывает, как быстро мы можем начать сборку деталей, необходимых для разработки надежной стратегии сопоставления. Это два возможных элемента, которые вы могли бы использовать как часть стратегии сопоставления по нескольким критериям.
Еще раз, к следующему…
