Есть задача: Найти в строке наборы одинаковых букв известного размера, например, в строке ааа123ббб456ввв78912а34б56 это а123/12а3 и б456/4б56.
Мой подход, последовательно сдвигая основной индекс по строке, хэшировать, и двигаться по строке хэшируя отрезки. Проблема в функции хэширования, есть ли такая, которая дает коллизии на состав букв?
Здравствуйте, morm, Вы писали:
M>Есть задача: Найти в строке наборы одинаковых букв известного размера, например, в строке ааа123ббб456ввв78912а34б56 это а123/12а3 и б456/4б56.
M>Мой подход, последовательно сдвигая основной индекс по строке, хэшировать, и двигаться по строке хэшируя отрезки.
1. перед хешем сортировать буквы
2. поддерживать сортировку легко двигаясь по 1 (одним пробегом по текущему списку, удалять предыдущий и добавлять следующий)
Здравствуйте, morm, Вы писали:
M>Есть задача: Найти в строке наборы одинаковых букв известного размера, например, в строке ааа123ббб456ввв78912а34б56 это а123/12а3 и б456/4б56.
M>Мой подход, последовательно сдвигая основной индекс по строке, хэшировать, и двигаться по строке хэшируя отрезки. Проблема в функции хэширования, есть ли такая, которая дает коллизии на состав букв?
M>Заранее спасибо.
Здравствуйте, morm, Вы писали:
M>Есть задача: Найти в строке наборы одинаковых букв известного размера, например, в строке ааа123ббб456ввв78912а34б56 это а123/12а3 и б456/4б56.
M>Мой подход, последовательно сдвигая основной индекс по строке, хэшировать, и двигаться по строке хэшируя отрезки. Проблема в функции хэширования, есть ли такая, которая дает коллизии на состав букв?
Можно заранее сделать Lookup-таблицу (массив), где для каждого символа будет некое n-битное число (можно случайное).
Например:
a -> 0xDD8AB2AE
b -> 0x96747107
c -> 0x10B28369
...
Т.е. при хешировании делать XOR не для кода символа, а для соответствующего числа из lookup-таблицы.
Здравствуйте, Caracrist, Вы писали:
C>1. перед хешем сортировать буквы
а) зачем хэш, если отсортировано все?
б) можно обойтись сортировкой "подсчетом", т.е. фактически, не использовать сортировку, а подсчитывать количество символов
C>2. поддерживать сортировку легко двигаясь по 1 (одним пробегом по текущему списку, удалять предыдущий и добавлять следующий)
При подсчете символов данный пункт превращается в уменьшение/увеличение счетчиков (удаляемого и следующего символа).
Б>а) зачем хэш, если отсортировано все? Б>б) можно обойтись сортировкой "подсчетом", т.е. фактически, не использовать сортировку, а подсчитывать количество символов
D>>ну видимо, проблема в размере "хэша".
Б>Не понял замечания...
ну как я понимаю, для чего используют хэш? Чтобы быстро сравнивать его на равенство/неравенство. И чтобы наиболее частый случай -- неравенство, обрабатывался бы как можно быстрее.
В твоем случае "хэш" фактически является набором счетчиков для каждого символа, такой хэш довольно таки объемный (не говоря о том что он плохо обобщается на уникод), и такие наборы счетчиков не так быстро сравниваются на равенство, как это возможно с более компактным хэщем. Наконец, хэши видимо где-то хранятся, чем больше он места занимает, тем хуже.
Здравствуйте, morm, Вы писали:
M>Есть задача: Найти в строке наборы одинаковых букв известного размера, например, в строке ааа123ббб456ввв78912а34б56 это а123/12а3 и б456/4б56.
Интересно, в рамках какой реальной задачи возникла такая подзадача?
Потому что, в данной формулировке она выглядит страшновато.
Для текста длиной T и алфавита мощностью S может потребоваться S*logT памяти и T² времени.
Допустим, текст = строка + перестановка(строка) -- предположение ранга (T/2)
Для проверки этой гипотезы нужно посчитать сигнатуры первой половины текста и второй половины текста.
Сигнатурой, в данном случае, будет вектор счётчиков (буква -> количество вхождений).
Мы можем для отсечки использовать какие-нибудь хэш-функции, нечувствительные к перестановке (например, сумма или ксор). Но, в случае совпадения хэша, придётся сделать честную проверку.
Очевидно, что если выполняется предположение (T/2), то вовсе необязательно, что выполняется и более слабое предположение (T/2)-1. Равно как и наоборот.
Так что придётся проверить все гипотезы, начиная с 2.
Хотя, мы можем ускориться.
Например, буква "а" встречается в позициях 1, 2, 3, 21. Это значит, что перестановки, содержащие эту букву, будут в позициях:
— длины 2 — 1, 2-1..2+1, 3-1..3+1, 21-1..21+1 (написал без отсечек по вылету за диапазон и по наложению)
— длины 3 — 1, 2-2..2+2, 3-2..3+2, 21-2..21+2
— длины 4 — 1, 2-3..2+3, 3-3..3+3, 21-3..21+3
и т.д.
Кстати говоря, нужно искать строго непересекающиеся наборы? А то, "а123а" можно трактовать как "а123"="123а"
Если для каждой буквы мы построим список её позиций (это потребует S*T*logT памяти и T времени), то, для каждой позиции P в тексте мы должны будем искать следующую подстроку в позиции max(next(P,ch)±L) где L — длина искомой подстроки, ch — символ из подстроки text[P..P+L).
С помощью таких прыжков мы сможем просканировать текст быстрее, чем за T.
Тут возможны разные стратегии.
Например, мы пробегаем по всем подстрокам, начинающимся с буквы "а", затем с буквы "б", и т.д.
В общем, надо подумать...
Здравствуйте, Кодт, Вы писали:
К>Интересно, в рамках какой реальной задачи возникла такая подзадача? К>Потому что, в данной формулировке она выглядит страшновато. К>Для текста длиной T и алфавита мощностью S может потребоваться S*logT памяти и T² времени.
Да это интересно, обязательно попробую.
Задача родилась из необходимости поиска ключа шифрования перебором слов исходного текста, без учета частот вхождения слов в текст. Просто хотел проверить насколько это неэффективно
Здравствуйте, morm, Вы писали: M>Мой подход, последовательно сдвигая основной индекс по строке, хэшировать, и двигаться по строке хэшируя отрезки. Проблема в функции хэширования, есть ли такая, которая дает коллизии на состав букв?
сумма
Здравствуйте, __kot2, Вы писали:
__>Здравствуйте, morm, Вы писали: M>>Мой подход, последовательно сдвигая основной индекс по строке, хэшировать, и двигаться по строке хэшируя отрезки. Проблема в функции хэширования, есть ли такая, которая дает коллизии на состав букв? __>сумма
Здравствуйте, morm, Вы писали:
M>Здравствуйте, __kot2, Вы писали:
__>>Здравствуйте, morm, Вы писали: M>>>Мой подход, последовательно сдвигая основной индекс по строке, хэшировать, и двигаться по строке хэшируя отрезки. Проблема в функции хэширования, есть ли такая, которая дает коллизии на состав букв? __>>сумма
M>куча коллизий на посторонние строки
вообще, я для себя давно понял, что когда речь идет о каком-то алгоритме, то нужно внимательно вдумываться во все ньюансы задачи.
например, поиск вхождения известной области в ДНК — казалось бы, поиск подстроки в строке и, значит, например, алгоритм Бойера-Мура (с википедии — Алгоритм Бойера — Мура поиска строки считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке). а нифига — облом, тормозить он будет не по детски, там чаще всего только 4 символа — actg, еще n особый символ и Бойер-Мур тут вообще весь косячится.
лобовое решение какое? пусть строка длинной 1000 (n), нужно найти все перестановки подстрок длинной 10 (m)
разбиваем весь текст на строки длинной 10 — их получится почти 1000 штук, потом сортируем каждую строку по буквам, то есть cat -> act, потом сортируем это все лексикографически и вуаля — три рубля — все готово.
нужно памяти O(n*m). для 1000 и для 10 сработает. а тут дальше вопросы начинаются — а насколько будет текст реальный больше 1000? а будет меньше 10 или больше? а сколько символов будет задействовано? а нужно ли регистр учитывать?
можно добавить хэширование — тогда будет то же самое, но сортировку финальную можно делать не по всем строкам а по каждому блоку. ну быстрее будет.
если хочется O(n) памяти, то можно хранить параллельно масив из n элементов, где хранить пред. позицию с совпадающим хэшем с текущей позицией.
какие варианты хэша возможны? сумма — самый простой и не очень хороший. дальше можно взять 26 бит в случае англ текста и пробить единички там если какие-то буквы есть. потом делим по модулю — получаем меньше. или в случае большего набора символов — например рус+анг+цифры — тут всяко делить придется и инт нужен уже в 64 бита. не идеально, так как повторы букв не учитывает, но очень неплох
Здравствуйте, morm, Вы писали:
M>Есть задача: Найти в строке наборы одинаковых букв известного размера, например, в строке ааа123ббб456ввв78912а34б56 это а123/12а3 и б456/4б56.
M>Мой подход, последовательно сдвигая основной индекс по строке, хэшировать, и двигаться по строке хэшируя отрезки. Проблема в функции хэширования, есть ли такая, которая дает коллизии на состав букв?
А почему бы не попробовать суффиксное дерево? Глубину ограничить этим самым известный размером, подстроки перед вставкой сортировать.
Перекуём баги на фичи!
