#algorithm
#алгоритм
Вопрос:
Это делается для автоматизации процесса тестирования. У меня есть два массива строк (извлеченных из двух разных источников для тестирования). Каждая строка в одном из массивов должна быть присвоена строке в другом массиве. Строки не всегда могут точно совпадать, но может существовать похожая строка (наилучшее совпадение), которую можно использовать. Если степень отклонения (основанная на процентах???) если это слишком много, то товар может быть соответствующим образом помечен.
Что мне нужно, так это алгоритм поиска НАИЛУЧШЕЙ строки и отклонения ее, если таковой нет.
Комментарии:
1. Количество и характер строк могут быть полезны для принятия решения о подходящем подходе. Например, если строки представляют собой слова, вы можете захотеть, чтобы изменение порядка слов имело большее значение, чем написание в слове, или, возможно, порядок слов неважен и лучше как раз наоборот. Некоторые дополнительные детали могут привести к лучшим предложениям.
Ответ №1:
Не существует алгоритма сравнения строк золотого стандарта («НАИЛУЧШЕГО»). Существует довольно много алгоритмов подобия строк, основанных на различных предположениях. Мера подобия принимает две строки и возвращает число, указывающее, насколько похожи строки.
Используя меру подобия, вы можете сравнить, насколько равны заданные строки со всеми строками в вашем массиве. Сходство — это число, и вы можете легко выбрать строку с наилучшим соответствием, даже когда данная строка и строка в массиве не идентичны.
Также возможно ввести порог отсечения, например, если ни одна строка не является достаточно похожей на заданную строку, ваш алгоритм может это обнаружить.
Популярной мерой подобия является расстояние Левенштейна, где подсчитывается количество изменений символов, добавлений и удалений для перехода от одной строки к другой.
Расстояние Левенштейна можно легко вычислить на c #, смотрите, например, эту ссылку для примера кода.
Комментарии:
1. :):) Я не ищу НАИЛУЧШИЙ алгоритм поиска строк, Vidstige…. Я имел в виду НАИЛУЧШЕЕ соответствие… Я решил сделать ударение на слове, поскольку я не собирался получать никаких точных совпадений для строк, кроме самых близких… Я бы использовал C #… Большое спасибо за немедленный ответ … 🙂
2. Да, я понимаю. Я обновил свой ответ, чтобы подробнее объяснить, как использовать меру подобия для выбора строки, наилучшим образом соответствующей. Надеюсь, это поможет 🙂
Ответ №2:
http://php.net/manual/en/function .levenshtein.php
Я думаю, что первый приведенный пример должен направить вас в нужное русло. Это для PHP, но алгоритм должен быть тем, который вы ищете.
Ответ №3:
Вы могли бы разбить строки на биграммы символов, генерируя вектор количества биграмм для каждой строки. Затем векторы можно сравнить, например, с косинусным подобием или аналогичной мерой. Тесно связанным является использование только имеющегося набора биграмм, сравнивая наборы с индексом Джаккарда.
Этот подход основан на статистике присутствующих биграмм, игнорируя порядок следования биграмм. В зависимости от характера ваших строк это может быть преимуществом или недостатком.
Комментарии:
1. Спасибо, Майкл… Поскольку я в основном тестировщик, я был бы признателен за дополнительные ресурсы (ссылки, статьи и т.д.)…