Какой самый быстрый способ найти похожие записи из разных (больших) источников данных

Question

Я работаю в агентстве общественного здравоохранения, у которого есть множество различных демографических наборов данных, хранящихся в серверах SQL, Access и Excel. Я написал приложение, которое позволяет людям находить «совпадения» в этих наборах данных на основе различных критериев, настроенных с помощью графического интерфейса пользователя. Например, одним «соответствием» может быть то, что First, Last и DOB совпадают в обоих наборах данных, но SSN «выключен на 1» (определяется алгоритмом Левенштейна).

Это большие наборы данных. Критерии соответствия могут быть действительно сложными. Прямо сейчас я нахожу совпадения, перетаскивая оба набора данных в таблицы данных в памяти, а затем перебирая строку за строкой в ​​первой таблице и проверяя, есть ли какие-либо строки во второй таблице, которые совпадают (используя LINQ). Так что мой код выглядит примерно так:

For each table1Row in TableOne/DatasourceOne
    table2Options=from l in table2rows where Levenshtein(table1Row.first, l.first)<2 //first name off by one            
    table2Options=from l in table2rows where Levenshtein(table1Row.last, l.last)<2 //last name off by one 
    if table2Options.count>1 then the row in table1 'matches' table 2      
Next 

Код выдает правильный вывод (находит совпадения), но он МЕДЛЕННЫЙ. Я знаю, что построчно работать медленнее, но использование LINQ для одновременного поиска всех записей идет еще медленнее.

From l in table1, k in table2 where Levenshtein(l.first, k.first)<2 and Levenshtein(l.last, k.last)<2 select l //this takes forever because it calculates the function for l rows * k rows 

Есть какие-нибудь идеи о том, как сделать это соответствие ядра быстрее?

Answer 1

Добавить и если заявление не проверять FirstName, если LastName не совпадает ..

99% из LastName не будут совпадать .. поэтому вы редко будете выполнять проверку имени. Это сократит ваше время обработки почти вдвое.

---

Еще одна вещь, которую вы можете сделать, это добавить больше правил (конечно, вы должны сделать это, сохраняя при этом целеустремленность), например: если вы добавите правило, чтобы сказать «Первая буква LastName должен совпадать ", вы можете сначала фильтровать по этому, что дает вам огромное повышение эффективности.

Answer 2

В статье Википедии о Левенштейне цитируется ряд возможных улучшений, которые должны помочь.В вашем случае, поскольку вас интересуют только расстояния ниже порогового значения, вы должны учесть, что если строки имеют одинаковый размер (например, номера социального страхования), вы можете использовать вместо этого расстояние Хэмминга.Для строк неравного размера вам нужно только вычислить диагональную полосу 2k + 1 в матрице, где k - ваш порог.

Запуск двух списков строк друг против друга должен обеспечить некоторую оптимизацию вАлгоритм Левенштейна.Например, сравнение замен слова, начинающегося с «а», будет применяться к всем словам, начинающимся с «а».Я посмотрю, смогу ли я найти эталонный алгоритм, который уже оптимизирует этот путь.

Answer 3

Я бы посоветовал перейти к какой-то реализации типа No-SQL. Возможно, вы захотите взглянуть на эту статью StackOverflow по NoSQL и Linq для получения дополнительной информации.

Если вы не можете использовать полноценную реализацию NoSQL, вам может потребоваться воспользоваться некоторыми идеями, такими как работа с парами ключ-значение для формирования связей между данными.

Answer 4

Не могли бы вы перенести все данные, которые нужно проанализировать, в память, а затем проанализировать их?Я заменил код следующим образом:

for each day in months:
     for each customer in customers:
          computed = computeSalesInDatabase(customer,day)
          saveComputed(computed)

На код, подобный следующему:

for each day in months:
     dailyData = getFullDay(day)
     for each customer in customers:
          computed = computeSalesInMemory(customer,day,dailyData)
          saveComputed(computed)

, и нашел его более производительным.