Правильность точности Misra-Gries на комбинированных потоках - PullRequest
Новая
       37

Правильность точности Misra-Gries на комбинированных потоках

0 голосов
/ 09 мая 2019

Я получил домашнее задание по точности алгоритма Мисры-Гриза объединенных потоков.Докажите, что точность объединенных потоков, по крайней мере, так же хороша, как и у сцепленного потокаПоэтому я пытался придумать примеры, чтобы лучше понять проблему.Я нашел следующее:

Предположим, что поток X = (a, a, b, b, c) и Y = (c, c, d, d, a) и k = 3

Применение Misra-Gries к X: 

| x_i || a      | a      | b      | b      | c      |
|-----||--------|--------|--------|--------|--------|
| d   || d[a]:1 | d[a]:2 | d[a]:2 | d[a]:2 | d[a]:1 |
|     ||        |        | d[b]:1 | d[b]:2 | d[b]:1 |

и к Y: 

| x_i || c      | c      | d      | d      | a      |
|-----||--------|--------|--------|--------|--------|
| d   || d[c]:1 | d[c]:2 | d[c]:2 | d[c]:2 | d[c]:1 |
|     ||        |        | d[d]:1 | d[d]:2 | d[d]:1 |

Затем в соответствии с Википедией я суммирую результаты и уменьшаю счетчики, пока не останется только k счетчик,Или, по словам моего лектора:

  1. Объедините два набора кандидатов, складывая частоты для одинаковых предметов.
  2. Вычтите частоту k-го наиболее часто встречающегося кандидата из всех оценок частоты.
  3. Удалите кандидатов с неположительными частотами.

Что приведет к незначительномуразличные резюме, но это не имеет значения в данный момент.Давайте возьмем подход Википедии:

  1. Суммируем:

d [a]: 1, d [b]: 1, d [c]: 1, д [д]: 1

Уменьшите до тех пор, пока не останется k счетчиков:

Каждый счетчик уменьшен на единицу, поэтому ни одного не осталось.

Следовательно, точность равна f1

Точность = 10/3

Теперь давайте проверим Мисры-Гри в объединенном потоке: 

| x_i | a      | a      | b      | b      | c      | c | c      | d      | d      | a      |
|-----|--------|--------|--------|--------|--------|---|--------|--------|--------|--------|
| d   | d[a]:1 | d[a]:2 | d[a]:2 | d[a]:2 | d[a]:1 |   | d[c]:1 | d[c]:1 | d[c]:1 | d[d]:1 |
|     |        |        | d[b]:1 | d[b]:2 | d[b]:1 |   |        | d[d]:1 | d[d]:2 |        |

Для точности: f2

Точность = 9/3

Что, на мой взгляд, точнее, чем запуск двух отдельных потоков и их объединение.Это, однако, противоречит утверждению, написанному в Википедии:

Выводы (массивы), выводимые алгоритмом, являются объединяемыми, в том смысле, что объединение сумм двух потоков s и r путем сложения их массивов по ключам изатем уменьшение каждого счетчика в результирующем массиве до тех пор, пока не останется только k ключей, приведет к итоговому результату того же (или лучшего) качества по сравнению с запуском алгоритма Мизра-Гриса по конкатенации s с r.

Так в чем же моя ошибка?

PS Я бы очень хотел предоставить изображения для этих формул, но мне не позволено, потому что репутация <10 .... </p>

...