Как оптимизировать получение минимального расстояния редактирования из большой таблицы в SQL? - PullRequest
Новая
       15

Как оптимизировать получение минимального расстояния редактирования из большой таблицы в SQL?

2 голосов
/ 22 мая 2010

У меня проблемы с оптимизацией этого вычисления расстояния Левенштейна, которое я делаю.Мне нужно сделать следующее:

  1. Получить запись с минимальным расстоянием для исходной строки, а также урезанную версию исходной строки

  2. Выбрать запись с минимальным расстоянием
  3. Если минимальные расстояния равны (оригинал и усеченный), выберите усеченную с наименьшим расстоянием
  4. Если все еще есть несколько записей, которые подпадают под две вышеуказанные категории, выберите ту, у которойсамая высокая частота

Вот моя рабочая версия: 

DECLARE @Results TABLE
(
    ID int,
    [Name] nvarchar(200), 
    Distance int, 
    Frequency int, 
    Trimmed bit
)


INSERT INTO @Results
    SELECT ID, 
           [Name], 
           (dbo.Levenshtein(@Source, [Name])) As Distance,
           Frequency, 
           'False' As Trimmed
    FROM
           MyTable

INSERT INTO @Results
    SELECT ID, 
           [Name], 
           (dbo.Levenshtein(@SourceTrimmed, [Name])) As Distance,
           Frequency, 
           'True' As Trimmed
    FROM
           MyTable

SET @ResultID = (SELECT TOP 1 ID FROM @Results ORDER BY Distance, Trimmed, Frequency)
SET @Result = (SELECT TOP 1 [Name] FROM @Results ORDER BY Distance, Trimmed, Frequency)
SET @ResultDist = (SELECT TOP 1 Distance FROM @Results ORDER BY Distance, Trimmed, Frequency)
SET @ResultTrimmed = (SELECT TOP 1 Trimmed FROM @Results ORDER BY Distance, Trimmed, Frequency)

Я считаю, что мне нужно сделать здесь, чтобы ..

  1. Не тупойрезультаты во временную таблицу
  2. Делайте только 1 выбор из `MyTable`
  3. Установка результатов прямо в операции выбора из первоначального оператора выбора.(Так как select установит переменные, и вы можете установить несколько переменных в одном операторе select)

Я знаю, что должна быть хорошая реализация этого, но я не могу понять это ... этонасколько я понял: 

SELECT top 1 @ResultID = ID, 
             @Result = [Name], 
            (dbo.Levenshtein(@Source, [Name])) As distOrig,
             (dbo.Levenshtein(@SourceTrimmed, [Name])) As distTrimmed,
             Frequency
FROM
    MyTable
WHERE /* ... yeah I'm lost */
ORDER BY distOrig, distTrimmed, Frequency

Есть идеи?

1 Ответ

0 голосов
/ 22 мая 2010

Я думаю, что ваша попытка отличается от кода, который, как вы говорите, работает, в том, что рабочий код сначала упорядочивается по расстоянию, независимо от того, является ли это исходным или сокращенным расстоянием. Ваша попытка сначала упорядочивается по исходному расстоянию, а затем усекается.

Я не уверен, что понимаю, что вы пытаетесь сделать целиком, но делает ли следующее то, что вам нужно? 

SELECT TOP 1
    @ResultId = ID,
    @Result = [Name],
    @ResultDist = distOrig,
    @ResultTrimmed = distTrimmed
FROM (
    SELECT
        ID, [Name], 
        dbo.Levenshtein(@Source, [Name]) As distOrig,
        dbo.Levenshtein(@SourceTrimmed, [Name])) As distTrimmed,
        Frequency
    FROM MyTable
) AS T
ORDER BY
    CASE WHEN distOrig > distTrimmed THEN distOrig ELSE distTrimmed END, -- Distance
    CASE WHEN distOrig > distTrimmed THEN 1 ELSE 0 END,                  -- Trimmed
    Frequency                                                            -- Frequency
...