Приближенное сравнение регулярных выражений: различия между версиями

О некоторых недавних экспериментах сообщается в работе [ ]. Для малых значений m и k, и предполагая, что все веса равны 1 (за исключением w(c ! c) = 0), битово-параллельные алгоритмы с наихудшей сложностью O(kn(m/log n)2) [4 , 9] являются самыми быстрыми (второй из них способен пропускать некоторые символы текста в зависимости от R). Для произвольных целочисленных весов наилучшим выбором является более сложный битово-параллельный алгоритм [ ] либо алгоритм на основе метода «четырех русских» [10] для больших значений m и k. Первоначальный алгоритм [3] работает медленнее, однако только он поддерживает произвольные веса.