Levenshtein (или Damerau-Levenshtein, если возможно!) Distance is Assembly

Question

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

Answer 1

Вы можете легко использовать BK-tree, чтобы создать дерево поиска, если Levenshtein достаточно. Дамарау-Левенштейн can not be used with a metric tree.

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

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