Расстояние Левенштейна (или Дамерау-Левенштейна, если возможно!) - это сборка

Question

У меня есть программа, в которой мне нужно несколько раз вычислить расстояние Левенштейна между парами слов (одно из них фиксированное), и несколько раз может варьироваться от 1000 до 120000 для каждого фиксированного слова.Поскольку я хочу максимально оптимизировать эту программу, я подумал о реализации этих вычислений в сборке.Проблема в том, что я ничего не знаю об ассемблере, кроме теории, и что она может представлять большие улучшения скорости.Может ли кто-нибудь помочь мне или предоставить код сборки для этого расстояния?Кроме того, как я могу вызвать сборку из модуля C #?

Answer 1

Вы можете легко использовать BK-дерево для создания дерева поиска, если Левенштейна достаточно.Damarau-Levenshtein нельзя использовать с деревом метрик .

Вам не нужно писать эту реализацию на ассемблере или C #, вы можете далеко продвинуться, используя небезопасный код и указатели.

• Чтение и кеширование str.Length, это вызовы методов (наиболее вероятно, встроенные / оптимизированные)
• Доступ к строкам с помощью указателей.
  fixed(char* ptrX=strX, ptrY=strY) ...
• Вы можетесоздайте свою таблицу / массив / состояние как int [строки * столбцы] вместо int [строки] [столбцы] и используйте указатели для чтения / записи.
  int[] state = new int[rows*cols]fixed(int* ptrState=state)
• Вам не нужно больше двух строк в таблице состояний, у вас есть та, из которой вы читаете, и та, в которую вы пишете.Затем поменяйте местами указатели и прочитайте то, что вы только что написали.
• Я полагаю, что вы можете оптимизировать, удалив идентичные префиксы / суффиксы
  L('catz', 'cats') == L('z', 's') == 1
L('rats', 'cats') == L('r', 'c') == 1