Лучший способ сортировки списка строк на основе отличий от целевой строки?

Question

Мне нужно отсортировать список на основе разницы между строками в списке и целевой строкой.

Как лучше всего реализовать алгоритм сортировки такого типа?

Меня не очень заботит производительность, но коллекция потенциально может стать большой (скажем, полмиллиона вершин).

Любая помощь приветствуется!

Answer 1

Я бы порекомендовал вычислить расстояние Левенштейна , а затем просто упорядочить по целому результату. ( Магический код )

public void Example()
{
    string target = "target";

    List<string> myStings = new List<string>();

    myStings.Add("this");
    myStings.Add("that");

    myStrings = myStrings.OrderBy(each => Levenshtein(each, target)).ToList();
}

public int Levenshtein(string stringA, string stringB)
{
    // Magic goes here
    return 0;
}

Без OrderBy для старых ребят из skool 2.0?

List<string> myStrings;
myStrings.Sort(LevenshteinCompare);
...

public class LevenshteinCompare: IComparer<string>
{
    public int Compare(string x, string y)
    {
        // Magic goes here
    }
}

Answer 2

Как лучше всего реализовать алгоритм сортировки такого типа?

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

Это, конечно, не полезный ответ. Почему бы и нет? Потому что то, что вы действительно хотите знать, это «Какая метрика разницы для строк?»

Ответ на вопрос real , к сожалению, «зависит»; это зависит от того, какие свойства расстояния вам небезразличны.

Как говорится, прочитайте о расстоянии Левенштейна и что он действительно говорит о струнах.

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

Вы также можете использовать алгоритм Soundex, который говорит о том, какие строки звучат одинаково (но это лучше всего подходит для коротких строк; я не знаю, какой тип ввода вы используете).

Если строки имеют одинаковую длину, вы также можете использовать расстояние Хэмминга (посчитать количество индексов, в которых строки отличаются). Вероятно, это можно обобщить до что-то , считая (в одностороннем порядке) несуществующие индексы как всегда разные, что дает вам нечто похожее на Левенштейна (может быть, своего рода 'sorta').

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