Обзор редакционных расстояний и алгоритмов их вычисления

[Oleg Sychev]

Originally reported on Google Code with ID 69 ``` Тема вашей дипломной работы подразумевает проведение серьезного обзора существующих редакционных расстояний и алгоритмов их вычисления. С указанием их целей, основных свойств, затрат на вычисление.

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

Черновики обзора лучше приносить на встречу в распечатанном виде. Задача здесь создана главным образом для того, чтобы вы видели свои задачи и никто о них не забыл... ```

Reported by `oasychev` on 2011-11-28 21:15:43

[Oleg Sychev]

``` Чтобы работа не стопорилась делайте обзор одного расстояния (алгоритма) в неделю.

В обзор обязательно включите степень его полезности для определения искомых нами ошибок и алгоритмическую сложность вычисления (оценки большого О). ```

Reported by `oasychev` on 2011-12-07 23:21:35

[Former user]

``` Сейчас работа несколько застопорилась из-за того, что пока довольно мало найдено подобных расстояний. На данный момент более менее найдены описания для расстояний Хэмминга и Левенштейна. Однако я нашёл некоторые алгоритмические приёмы для вычисления расстояний различными способами. Стоит ли их включить в исследование? ```

Reported by `mamontov.dp` on 2011-12-13 15:59:00

[Oleg Sychev]

``` Для каждого расстояния лучше всего включить описание наиболее эффективного алгоритма... ```

Reported by `oasychev` on 2011-12-14 11:25:56

[Former user]

``` Не стоит ли также рассмотреть алгоритмы выравнивания строк? На эту тему значительно больше материала, а также это тесно связано с вычислением расстояния и LCS. ```

Reported by `mamontov.dp` on 2012-01-29 16:17:16

[Former user]

``` Решил описать текущие критерии рассмотрения алгоритмов: 1. Применимость к задаче вычисления редакционных правок 2. Алгоритмическая сложность вычислений и затраты памяти. 3. Сфера применения (имеется ввиду первичная отрасль науки, в которой применяется, соответственно исходя из этого можно оценить применимость к нашей задаче). ```

Reported by `mamontov.dp` on 2012-02-04 16:22:30

[Former user]

``` Мне кажется или это issue стоит лучше закрыть? Ибо работа была выполнена, а в этом направлении больше исследование вестись не будет. ```

Reported by `mamontov.dp` on 2012-09-25 17:18:16

[Oleg Sychev]

``` Можете поставить его в Fixed если считаете выполненным, но я пока не буду закрывать в Done пока не смогу провести контрольного поиска сам - вдруг еще чего найду...

Переписываю на себя поэтому ```

Reported by `oasychev` on 2012-09-30 19:26:14

[Oleg Sychev]

Устарело.