Алгоритм поиска и назначения ЛУЧШЕЙ строки для каждого элемента массива строк (из другого массива строк)

Question

Это для автоматизации процесса тестирования.У меня есть два строковых массива (извлеченные из двух разных источников для тестирования).Каждая строка в одном из массивов должна быть назначена строке в другом массиве.Строки могут не всегда соответствовать точно, но может быть похожая строка (наилучшее соответствие), которая может быть использована.Если степень дисперсии (в процентах ???) слишком велика, то элемент можно соответствующим образом пометить.

Мне нужен алгоритм поиска строки BEST и отклонения того же, если нет 'т любой.

Answer 1

Алгоритм сравнения строк без золотого стандарта ("BEST"). Существует довольно много строковых алгоритмов подобия , основанных на различных предположениях. Мера подобия принимает две строки и возвращает число, указывающее, насколько похожи строки.

Используя меру сходства, вы можете сравнить, насколько равны данные строки всем строкам в вашем массиве. Сходство - это число, и вы можете легко выбрать строку с наилучшим соответствием, даже , если данная строка и строка в массиве не идентичны .

Также можно ввести порог отсечки , например, если ни одна строка не похожа достаточно на данную строку, ваш алгоритм может обнаружить это.

Популярной мерой сходства является расстояние Левенштейна , где подсчитывается количество изменений, дополнений и удалений символов для перехода от одной строки к другой.

Расстояние Левенштейна можно легко вычислить в c #, см., Например, эту ссылку для примера кода.

Answer 2

http://php.net/manual/en/function.levenshtein.php

Я думаю, что первый пример должен привести вас в нужное русло. Это для PHP, но алгоритм должен быть тот, который вы ищете.

Answer 3

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

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