Обнаружение сходства строк с использованием расстояния Левенштейна (МЕДЛЕННО) - PullRequest
Новая
       30

Обнаружение сходства строк с использованием расстояния Левенштейна (МЕДЛЕННО)

4 голосов
/ 08 июля 2011

Запрос возвращает 21 миллион записей

То, как я перебираю эту таблицу, всегда Какие еще есть решения? 

SqlDataReader rd = DbInfo.DataRdr(Conn,
 "SELECT a.NAME AS ANAME, b.NAME AS BNAME, a.ID as AID, b.ID AS BUD " +
 "FROM myTable a JOIN myTable b ON a.NUM = b.NUM AND a.ID <> b.ID");

while (rd.Read())
{
   if (rd["ANAME"].ToString().LevenshteinDistance(rd["BNAME"].ToString()) <= 10)
   {

        Logging.Write(...);

   }
}



    public static int LevenshteinDistance(this string s, string t)
    {
        if (s == null)
            throw new ArgumentNullException("s");
        if (t == null)
            throw new ArgumentNullException("t");
        int n = s.Length;
        int m = t.Length;
        int[,] d = new int[n+1,m+1];

        if (n == 0 || m == 0)
            return Math.Max(m, n);

        for (int i = 0; i <= n; i++)
        {
            d[i, 0] = i;
        }
        for (int i = 0; i < m; i++)
        {
            d[0, i] = i;
        }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                int cost = (t[j] == s[i]) ? 0 : 1;

                d[i + 1, j + 1] = Math.Min(Math.Min(d[i, j + 1] + 1, d[i + 1, j] + 1), d[i, j] + cost);
            }
        }

        return d[n, m];
    }

Ответы [ 5 ]

3 голосов
/ 08 июля 2011

Вы сравниваете dt1.Rows[i]["Name"].ToString() с dt1.Rows[j]["Name"].ToString(), даже когда i == j.

Попробуйте зациклить 0 <= i < dt1.Rows.Count - 1 и i + 1 <= j < dt1.Rows.Count.

Кроме того, вы регистрируетесь, только еслиdt1.Rows[i]["NUM"].ToString() == dt1.Rows[i]["NUM"].ToString(), что, вероятно, является более быстрой проверкой.Нет смысла делать Левенштейна, если это неверно.

РЕДАКТИРОВАТЬ: @ Джон прав насчет dt1.Rows[i]["NUM"].ToString() == dt1.Rows[i]["NUM"].ToString() (оба i?).

3 голосов
/ 08 июля 2011

Вы можете начать с использования следующего запроса вместо этого, в зависимости от того, как часто столбцы NUM фактически равны: 

SELECT a.NAME AS ANAME, b.NAME AS BNAME, other things
FROM myTable a
JOIN myTable b
ON a.NUM = b.NUM
AND a.id < b.id

Тогда ваш запрос SQL выдаст вам пары строк с совпадающими NUM с, на которые вы можете позвонить LevenshteinDistance.Что-то вроде: 

DataTable dt1 = new DataTable();
dt1.Load(DbInfo.DataRdr(Conn, "[the query I wrote above]"));

for (int i = 0; i < dt1.Rows.Count; i++)
{
   if (dt1.Rows[i]["ANAME"].ToString().LevenshteinDistance(dt1.Rows[i]["BNAME"].ToString()) <= 10)
   {
     Logging.Write(...[modify the query so it returns the things you want to log]...);
   }
}
1 голос
/ 09 июля 2011

Самое большое улучшение, которое вы можете сделать, - это уменьшить пространство для решения. Поскольку вы хотите, чтобы максимальное расстояние составляло 10, любые строки, длина которых превышает 10, не могут быть квалифицированы: 

SELECT a.NAME AS ANAME, b.NAME AS BNAME, a.ID as AID, b.ID AS BUD 
 FROM myTable a JOIN myTable b ON a.NUM = b.NUM AND a.ID < b.ID
 WHERE length(a.NAME) - length(b.NAME) BETWEEN -10 AND 10;

Далее, профилируйте свой код и посмотрите, где находятся горячие точки. Хорошая статья: Найдите узкие места приложений с помощью Visual Studio Profiler .

И взгляните на Оптимизация алгоритма Левенштейна в C # .

Редактировать

Также Крис заметил, что с levenshtein(a,b) == levenshtein(b,a) вам нужно только выбрать при объединении a.ID

1 голос
/ 09 июля 2011

Оптимизация:

1) Посмотрите на ваши данные. Может быть, вы можете сделать несколько проверок, чтобы быстрее отсортировать недопустимые пары. Если длина Name изменяется более чем на 10, вы можете проверить, больше ли разница между s.Lenght и t.Length, и сразу же вернуться на большое расстояние (может быть int.MaxValue или просто 100). Нет смысла вычислять расстояние, если оно все равно явно выходит за рамки.

2) Ищите небольшие оптимизации. Зацикливание дважды на 150 тыс. Строк означает 22,5 млрд. Итераций. Небольшие изменения могут иметь большой эффект. Вы можете попытаться кэшировать объекты строк и удалить ToString(), используя метод Equals(). Я думаю, что это будет быстрее, чем доступ к i-му элементу вашей таблицы данных 150000 раз. 

for (int i = 0; i < dt1.Rows.Count; i++)
{
   var outerRow = dt1.Rows[i];
   for (int j = 0; i + 1 < dt1.Rows.Count; j++)
   {
     var innerRow = dt1.Rows[j];
     if (Equals(outerRow["NUM"] == innerRow["NUM"]))
     {
        if (outerRow["Name"].ToString().LevenshteinDistance(innerRow.ToString()) <= 10)
        {
           Logging.Write(...);
        }
     }
  }

3) Попробуйте уменьшить / разделить наборы данных. Выполните запрос, чтобы получить все возможные значения NUM select distinct NUM from myTable. Затем для каждого NUM в вашем результате выполните исходный запрос, но с использованием условия where и выберите только имя: SELECT name from myTable where NUM = currentNum.

Таким образом, вы не t have to compare the NUM row and you don t выбираете нечетные данные. Ваш код может быть оптимизирован для выполнения только расстояния Левенштейна, но с использованием оптимизаций, указанных в 1 + 2.

4) Попробуйте другой подход, например, полнотекстовый поиск.

Я просто хочу решить подобную проблему, находя совпадения в таблице с 1,2 миллионами строк. Я использовал lucene.net , который дает мне результаты в реальном времени при поиске по одному или нескольким свойствам моих строк.

Они тоже работают на levenshtein, но, возможно, это быстрее, чем ваша реализация;) MSSQL Server также поддерживает полнотекстовый поиск.

0 голосов
/ 08 марта 2012

После выполнения других оптимизаций, упомянутых в этом потоке, вы можете перенести вычисление Левенштейна на сервер и выбрать только те строки, которые соответствуют вашим критериям редактирования расстояния. Мне нужна была эта функциональность в проекте, поэтому я сделал из нее библиотеку, здесь . Метод редактирования расстояния, используемый в lib, требует только n * 2 памяти вместо n * m.

Например, даже на сервере вы хотите выполнять вычисления EditDistance только тогда, когда разница в длине строки <10, поэтому сначала проверьте это. Что-то вроде </p> 

SELECT a.NAME as NameA, b.NAME as NameB
FROM table a
JOIN table b ON a.NUM = b.NUM
WHERE a.Id < b.Id
AND length(a.NAME) - length(b.NAME) BETWEEN -10 AND 10 OR
    EditDistance(a.Name, b.Name) < 10
...