Наибольший общий префикс при наличии ошибок
А какого рода ошибки?
Как в примере. Строки, случайно попавшие в общую группу, но имеющие другой префикс. Для определённости, пусть доля таких ошибок не больше p. Или пусть у таких ошибок префикс совпадает с общим не больше, чем на n символов, в то время как правильный префикс не короче m.
Например:
123459999
123450000
123450123
123459876
127777777
127333333
Правильный префикс — 12345. Известно заранее, что он не короче m=4 символов (в данном случае, 5 а ошибочная строка совпадает с остальными лишь на максимум n=2 символа. Как можно учесть это, чтобы эффективно отсеить две неправильных строки?
Или: если проигнорировать 2 строки (то есть 33% <= p = 40% допустимых ошибок то длиннейший суффикс будет 12345.
Как можно использовать одно или оба этих соображения? Есть ли готовые (придуманные) алгоритмы? Число строк может быть довольно большим, порядка сотен, а наборов таких строк — миллионы, так что хотелось бы чего-нибудь поинтеллектуальнее перебора всех возможных суффиксов.
Например:
123459999
123450000
123450123
123459876
127777777
127333333
Правильный префикс — 12345. Известно заранее, что он не короче m=4 символов (в данном случае, 5 а ошибочная строка совпадает с остальными лишь на максимум n=2 символа. Как можно учесть это, чтобы эффективно отсеить две неправильных строки?
Или: если проигнорировать 2 строки (то есть 33% <= p = 40% допустимых ошибок то длиннейший суффикс будет 12345.
Как можно использовать одно или оба этих соображения? Есть ли готовые (придуманные) алгоритмы? Число строк может быть довольно большим, порядка сотен, а наборов таких строк — миллионы, так что хотелось бы чего-нибудь поинтеллектуальнее перебора всех возможных суффиксов.
Ты имеешь в виду, что некоторые, более одной, строки начинаются с этого префикса, а некоторые могут не начинаться?
Строишь префиксное дерево, берешь ветвь, в которой больше одного листа, с самым длинным начальным ключом.
Строишь префиксное дерево, берешь ветвь, в которой больше одного листа, с самым длинным начальным ключом.
если без ошибок, то используют префиксное дерево ( http://en.wikipedia.org/wiki/Trie )
я думаю можно и в твоем случае использовать
выделить наиболее вероятные префиксы, потом оставшиеся проверять на удаленность от наиболее вероятных
http://en.wikipedia.org/wiki/Approximate_string_matching
http://en.wikipedia.org/wiki/Edit_distance
я думаю можно и в твоем случае использовать
выделить наиболее вероятные префиксы, потом оставшиеся проверять на удаленность от наиболее вероятных
http://en.wikipedia.org/wiki/Approximate_string_matching
http://en.wikipedia.org/wiki/Edit_distance
Точнее, тебе нужна самая тяжелая ветвь из тех, у которых начальный ключ не меньше заданной длины.
всем спасибо
если p < 0.5, то достаточно фильтровать по самому частому символу
на i-м месте искомый символ встречается в более половниы случаев, значит находится однозначно за один проход.
Если p >= 0.5, то да, надо Trie строить.
на i-м месте искомый символ встречается в более половниы случаев, значит находится однозначно за один проход.
Если p >= 0.5, то да, надо Trie строить.
Оставить комментарий
Inflict84
Дан набор строк, которые должны начинаться с какой-то последовательности.Нужно найти эту последовательность — наидлиннейший общий префикс. Осложнение: в исходном списке могут быть ошибки.
Например, дан набор:
ABCDCDEFGHHG
ABCDCQRFBZY
ABZYXFGDGDGD
ABCDCDEXYZWVU
YIURTHJKHKHF
ABCDCHSDHKHKJ
Нужно найти префикс ABCDC
ABCDCDTSQWER
Куда смотреть?
Спасибо