Какова вероятность, что X *последовательный* биты в массиве битов N установлены на 1?
Если вы стремитесь к более быстрому коду, который зависит от текстового окна, вы можете пойти на поиски по множеству, чтобы ускорить процесс. Если возможно, замените список поиска на набор, а затем найдите все возможные окна в тексте, которые будут использоваться для поиска.
def getAllWindows(L):
tracker = set()
for w in range(1, len(L)+1):
for i in range(len(L)-w+1):
sub_window = L[i:i+w]
if sub_window not in tracker:
tracker.add(sub_window)
yield sub_window
lookup_list = ['red', 'hello', 'how are you', 'hey', 'deployed']
lookup_set = set(lookup_list)
text = 'hello, This is shared right? how are you doing tonight'
result = [sub_window for sub_window in getAllWindows(text) if sub_window in lookup_list]
print(result)
#Output:
['red', 'hello', 'how are you']
5 ответов
Если Вы хотите, чтобы быстрый тест видел, случайна ли последовательность битов на основе самой длинной полосы 1's, можно использовать то, что ожидаемая самая длинная полоса 1's в битах N является Θ (журнал (N)).
Кроме того, вероятность, что самая длинная полоса превышает r*log ₂ (N) биты, в большей части 1/N^ (r-1) и так же вероятности, что самая длинная полоса является меньше, чем журнал ₂ (N)/r биты в большей части 1/N^ (r-1).
Эти результаты получены в разделе по "Полосам" в главе по "Подсчету и Вероятности" во Введении в Алгоритмы
Править: Ниже не отвечает на вопрос, извините... Комментарий разъяснил, что настоящая проблема о вероятности x 1 с подряд из n битов, не только простой вещи, которую я принял. Имел беглый взгляд на это: http://www.mathhelpforum.com/math-help/probability-statistics/64519-probability-consecutive-wins.html, который может быть тем, что Вы ищете - это, кажется, имеет дело с разработкой, что вероятность выполнения toin устраивается из более многочисленного населения toin, устраивается, так подобные звуки. Но ее последнее и я устали так, я не декодировал математику :)
УСТАРЕВШИЙ: Это кажется, что Вы в основном имеете дело с имеющей два названия вероятностью - см. http://en.wikipedia.org/wiki/Binomial_probability.
Я должен признать, что не делал вычислений в течение приблизительно 20 лет, настолько несколько ржавых...
В основном, имеющий два названия позволяет Вам тому, "добавьте вместе" вероятность события, происходящего многократно, где существует только два возможных результата каждый раз. Порядок является значительным в Вашем случае, таким образом, это должно быть столь же просто как умножение вероятностей;
Для 1 бита это - 50%
Для 2 битов это - 50%^2 = 25%
Для 3 битов это - 50%^3 = 12,5%
Посмотрите на него иначе;
1 бит только имеет 2 возможных комбинации, одна из которых составляет всю 1 с = 50%
2 бита имеют 4 возможных комбинации (10, 01, 11, 00), только один из которых составляет всю 1 с - так 25%
3 бита имеют 2^3 = 8 возможных комбинаций, только одна из которых составляет всю 1 с, таким образом, 1/8 = 12,5%
Так... вероятность n битов весь являющийся 1 = 1 / (2^n).
Хорошо, вот то, что я нашел:
P = 1 - Q (X)
где
Q (X) = [1 - 1/2 (Z)] / [(X + 1 - XZ) x 1/2 x Z^(X+1)]
где
Z = 1 + (1/2) (1/2) ^X + (X+1) [(1/2) (1/2) ^X] ^2 +...
Ссылка с частью математики здесь:
можно сделать рекурсивную программу (Python):
prob (x, n) дает Ваш желаемый результат
import math
def prob(x,n,i=0):
if i == x: return 1
if (x+i) > n: return 0
t = .5 * prob(x,n-1,i+1) + .5 * prob(x,n-1,i)
return t
Мой подход к этому должен был бы определить FSA, который принимает комбинации двоичных разрядов корректного типа, и затем моделируйте шаблон для каждого числа битов. т.е.
State state_map[] = {
0 => { 0 -> 0; 1 -> 1; accepts = false },
1 => { 0 -> 0; 1 -> 2; accepts = false },
2 => { 0 -> 0; 1 -> 3; accepts = false },
3 => { 0 -> 3; 1 -> 3; accepts = true }
};
state[t: 0, s: 0] = 1.0;
state[t: 0, s: 1] = 0.0;
state[t: 0, s: 2] = 0.0;
state[t: 0, s: 3] = 0.0;
for (t = 0; t < N; t++)
for (s = 0; s<NUM_STATES; s++)
state[t: t+1, s: state_map[s].0] += state[t, s] * .5
state[t: t+1, s: state_map[s].1] += state[t, s] * .5
print "Probability: {0}", state[t: N, s: 3],