ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Vadim Meshkov                        2:5020/400     09 Jan 2002  21:28:46
 To : Starikov Alexander
 Subject : Re: Строки --- вопрос снят?
 -------------------------------------------------------------------------------- 
 

 Andrew Simontsev 
 <Andrew.Simontsev@p41.f115.n5005.z2.fidonet.org> начал 
 когда-то дискуссию о "минимальном слове" заведомо не 
 содержащемся в данной строке. Хочется издать еще 
 несколько возгласов по этому поводу.
 
 Пусть длина строки --- N, длина алфавита --- n, длина 
 слова --- m.
 
 1)  Предположим, что строка не структурирована, т.е. 
 представляет собой случайный набор символов. Посчитаем 
 вероятности. В заданной строке можно выделить N слов 
 длины m (точнее N-m+1, но мы считаем, что N гораздо 
 больше m). С алфавитом длины n всего можно составить n^m 
 различных слов длины m.
 Рассмотрим модельную задачу: дано число (набор цифр 
 0,1,...,9) длины N. Какова вероятность, что в этом числе 
 ни разу не встречается, скажем, цифра 8? Вероятность, 
 что первая цифра числа не восьмерка, равна (1-1/10).
 Аналогично и для всех остальных позиций. 
 Итог: P=(1-1/10)^N. Возвращаясь к нашей строке, 
 заключаем, что с вероятностью
    
         P(m) = (1-1/n^m)^N
 
 найдется слово длины m, которое не содержится в данной 
 строке. Применительно к решаемой задаче P(m) --- 
 вероятность того, что "минимальное слово" имеет длину
 <= m (поскольку, если уж нашлось требуемое слово длины 
 m, то подавно найдутся и более длинные). Следовательно, 
 ВЕРОЯТHОСТЬ Q(m), ЧТО "МИHИМАЛЬHОЕ СЛОВО" ИМЕЕТ ДЛИHУ m, 
 РАВHА
    
          Q(m) = P(m)-P(m-1).
 
 Приведу некоторые данные для строки из 100 миллионов 
 (N=10^8) символов, для алфавитов разной длины (n)
    
    n=2 (бинарный алфавит)
        Q(23)=2.57e-3  Q(24)=4.82e-2  Q(25)=1.75e-1  Q(26)
 =2.49e-1
        Q(27)=2.14e-1  Q(28)=1.41e-1  Q(29)=8.10e-2  Q(30)
 =4.34e-2
    n=4
        Q(12)=2.58e-3  Q(13)=2.23e-1  Q(14)=4.65e-1  Q(15)
 =2.22e-1
        Q(16)=6.59e-2  Q(17)=1.72e-2  Q(18)=4.35e-3
    n=8
        Q(8)=2.58e-3   Q(9)=4.72e-1   Q(10)=4.36e-1  Q(11)
 =7.74e-2
        Q(12)=1.01e-2  Q(13)=1.27e-3
    n=16
        Q(6)=2.58e-3   Q(7)=6.86e-1   Q(8)=2.88e-1   Q(9)
 =2.16e-2
        Q(10)=1.36e-3
    n=32
        Q(5)=5.08e-2   Q(6)=8.60e-1   Q(7)=8.60e-2   Q(8)
 =2.82e-3
    n=64
        Q(4)=2.58e-3   Q(5)=9.08e-1   Q(6)=8.75e-2   Q(7)
 =1.43e-3
    n=128
        Q(3)=1.9e-21   Q(4)=6.89e-1   Q(5)=3.08e-1   Q(6)
 =2.88e-3
    n=256
        Q(3)=2.58e-3   Q(4)=9.74e-1   Q(5)=2.29e-2   Q(6)
 =9.06e-5
 
 Диапазон наиболее вероятных длин сужается с увеличением 
 длины алфавита n. Как следует, например, из последней 
 строки, для ASCII-строки длиной 10^8 минимальное слово 
 будет с вероятностью 0.97 состоять всего из четырех 
 символов. Даже для бинарного алфавита (n=2) слово имеет 
 длину 25-28 бит.
 
 2) Hе сумев преодолеть любопытство, я таки реализовал 
 второй из предложенных ранее алгоритмов.
 
 > Запасаешься копиями алфавита. Берешь в руку первую 
 
 копию, бежишь и
 
 > выкидываешь буквы, которые встречаешь в строке. Когда 
 
 в этой копии остается
 
 > одна буква, объявляешь ее первой буквой своего 
 
 слова. ... Достаешь вторую
 
 > копию, бежишь и смотришь теперь на буквы, которые 
 
 следуют за вхождениями
 
 > первой. Выкидываешь эти буквы из алфавита, пока не 
 
 останется одна.
 
 > Присоединяешь ее к первой ... и т.д.
    
 Проделав огромное число прогонов, у с удовольствием 
 обнаружил, что алгоритм выдает результаты в превосходном 
 соответсвии с изложенной теорией. При этом для алфавитов 
 
 n>=32 практически никогда не бывает, чтобы получалось 
 
 более двух различных длин (например, m=4 и m=5). Поэтому 
 есть очень большая уверенность, что результат отличается 
 от "истинно оптимального" максимум на единицу.
 
 3) Постфактум можно уточнить трудоемкость алгоритма: ~ 
 (m-1)*N сравнений, где m --- длина найденного 
 минимального слова.
 А суффиксное дерево все качалось на ветру ... :)
 
 Извиняюсь за чрезмерный объем.
 С уважением к собравшимся, В.М.
 
 -- 
 Отправлено через сервер Talk.Ru - http://www.talk.ru
 --- ifmail v.2.15dev5
  * Origin: Talk.ru (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: срочно нужен алг.   Starikov Alexander   09 Jan 2002 11:33:51   Re: Строки --- вопрос снят?   Vadim Meshkov   09 Jan 2002 21:28:46