Оценки величины среднего покрытия словаря (стр. 1 )

Оценки величины среднего покрытия словаря

В статье даны грубые оценки величины среднего покрытия словаря базисом ограниченного размера

В [1] сформулирована задача разложения «словаря» (множества слов, содержащего повторы) на базис — набор строк, такое разложение допускающий. На размер базиса наложено априорное ограничение. Все слова (основы) разделены в [1] по первой букве слова на А–словарь, Б–словарь и т. д.. Слова в организованных так словарях хранятся без первой буквы. Эти сведения об устройстве словарей понадобятся только для понимания, о каких объектах идет речь, и никаким иным образом на дальнейшее изложение не влияют.

Будем называть l–словом слово (основу) длиной l. Базисом B словаря V назовем любой набор строк, такой что каждое словарное слово представимо в виде конкатенации строк этого набора (разложимо на него). Назовем m–разложением основы ее разложение по базису, содержащее m, в том числе «одноименных», компонент. Минимальным разложением называется такое, что разложения на меньшее число компонент в данном базисе не существует. Длиной минимального разложения основы будем называть число компонент в нем. Средним покрытием M(B, V) базисом B слов словаря V назовем отношение суммы длин всех основ к сумме длин их минимальных разложений, то есть среднее число символов покрываемое одной компонентой базиса.

Как следует из определения базиса, худшее значение среднего покрытия M(B, V) равно 1, что соответствует использованию в качестве базиса самого алфавита (предполагается, что размер алфавита заведомо меньше допустимого размера базиса). Найдем грубую верхнюю оценку M(B, V).

Схема получения этой оценки состоит в том, чтобы для каждого l£L (L — маскимальная длина основы) выяснить, какую часть всех l–строк составляют наиболее частые и выбрать такое «покрытие» словаря комбинацией из скольких-то лучших L–, (L–1)–, …, 4–, 3– и 2–строк, при котором бы максимизировалась величина M(B, V). То есть сначала словарь покрывается «лучшими» строками большей длины, оставшаяся часть словаря — «лучшими» строками меньшей длины и т. д.

Сразу скажем, что в этой схеме допускаются три огрубления, из которых только последнее заведомо завышает полученную оценку.

Первое. То как выбираются наиболее частые строки одной длины. Если использовать в качестве показателя частости частоту строки среди всех строк такой же длины, не учитывая позиции, с которых эти строки встречаются в словах, то мы рискуем ничего не узнать о том, сколько символов покроет набор из скольких-то таких строк. Например, пусть есть «слова» 12346 и которые мы покроем непересекающимися 3–строками. Вхождения 3–строк в слова: трижды 234, по два раза 123, 345 и 456 и по одному разу 346 и 523. Лучшее покрытие одной строкой дает строка 234, покрывающая в общей сложности 9 символов. Однако в наборы лучшего покрытия из 2 и 3 строк именно эта строка как раз и не войдет! Такими лучшими наборами будут <123, 456>, покрывающий 12 символов, и <123, 456, 523>, покрывающий 15 символов.

Значит, что построение лучшего набора из n строк не может состоять в срезке «наиболее частых» n строк, а лучший набор большего размера не обязательно включает в себя лучшие наборы меньших размеров. (В действительности, с ростом n изменения в составе лучшего набора при переходе к следующему размеру все менее значительны.) Кроме того, процедура построения такого набора достаточно трудоемка и требует использования строгого алгоритма наподобие изложенного в гл. 5 [1]. Описанная ниже ранжировка строк одной длины среди не пересекающихся по расположению в словах лучше, чем ранжировка внутри всех строк одной длины, однако «лучшие n строк» по этой ранжировке не обязательно покрывают не меньшее число символов, чем действительно лучшие по покрытию n строк этой длины.

Второе огрубление, влияющее на оценку не обязательно в сторону завышения, состоит в неучете зависимости между строками разной длины (как избежать, одновременно завышая оценку покрытия, зависимости строк одной длины будет ясно при описании процедуры). Именно, покрыв часть словаря лучшими строками большей длины, мы тем самым покрыли ее и некоторыми из строк меньшей длины — как подстроками более длинных строк или их конкатенаций. В результате «апостериорная частость» строк меньшей длины снижается на число их появлений как подстрок уже покрытой части словаря. Достоверно от этого пострадают прежде всего не самые худшие строки, но не обязательно самые лучшие. И тогда суммарная частота скольких-то строк, стоящих в самом начале рангового распределения строк соответствующей длины, может даже возрасти, то есть улучшиться по сравнению с априорной, не учитывающей выбора строк большей длины.

Третье огрубление, почти наверняка перекрывающее два первых, — словарь в используемой процедуре рассматривается как единая строка–склейка, к тому же примерно одинаковая по своим свойствами во всех своих частях. Если бы нашей целью было получение более точной верхней оценки M(B, V), нам следовало бы рассмотреть слова разной длины по отдельности и подсчитать M(B, V) по Ml(B, V), найденным для каждого такого набора слов. Оставляем эту задачу в качестве упражнения и перейдем к описанию самой процедуры построения верхней оценки.

Назовем l–k–набором (где 0 £ k < l) множество всех различных l–строк, расположенных в содержащих их словах с позиции, по модулю l равной k. Это означает, что если взять l–строку, расположенную с k–й позиции слова, затем l–строку, стоящую следом за ней, и т. д., то такие строки попадут в один набор. Частость строки в наборе — число ее вхождений в слова, удовлетворяющие условию включения в набор.

Возьмем все слова длиной не меньше l. Построим по ним все l– k–наборы. Тем самым, частота строки среди строк из содержащего ее набора есть покрываемая ею при «l–k–замащивании» доля символов в допускающих такое покрытие словах. (Для сравнения, зная частоту какой-то строки среди всех строк той же длины, мы ничего не можем сказать, какую часть символов словаря покроет эта строки при l–k–замащивании. Единственное, что можно сказать, так это то, что частота l–строки среди всех l–строк есть средневзвешенная — по размерам l–k–наборов — от ее частот внутри наборов, а тем самым заведомо не больше максимальной частоты в наборах. При этом с увеличением l l–k–наборы для разных k все более разнятся, а суммарная частота самых частых среди всех l–строк все ниже аналогичной частоты по лучшему l–k–набору).

Ранжируем строки внутри каждого из наборов по убыванию частоты. Разобьем полученный список на интервалы с каким-то шагом, например, 16. Тогда можно сказать, какую часть из покрываемого k–l–замащиванием числа символов покрывают наиболее частные 16, 32, 48 и т. д. l–строк из соответсвующего набора.

С ростом k число строк в l–k–наборе уменьшается (например, на двух словах длиной соответственно 6 и 12 имеем 10 5–строк, из которых в 0–й набор попадут 3 строки, в 1–й — также 3, во 2–й — 2, а в 3–й и 4–й лишь по одной). Поэтому при фиксированном l лучшее распределение величины покрытости может оказаться у большего k лишь из-за того, что ему соответствует меньшее число различных l–строк и тем самым первые n наиболее частых строк покроют большую долю, чем при большем числе различных строк. Такой эффект возникает на небольших наборах. На словарях, включенных в табл. 1, он не заметен.

В табл. 1 приведены относящиеся к некоторым словарям (А–словарю, Б–словарю и т. д.) данные о том, какая часть символов не покрыта первыми строками из ранжированных l–k–наборов. Размер порции равен 16, то есть, скажем, пяти порциям соответствуют самые частые 80 строк данного набора. Столбец «число всех l–строк» содержит общее число вхождений всех строк набора в те слова, которые допускают «замащивание» l–строками, стоящими в позициях k (mod l).

Табл 1. Доля символов, непокрытых наиболее частыми строками l–k–наборов, и доля всех l–строк, непокрытых наиболее частыми из них

Перваябуква	l–k–индекснабора	Число всех l–строк	Доля непокрытых первыми R порциями (в процентах)
1	2	3	4	5	6	7	8	9	10	11	12
	2–0	11646	73	58	46	38	31	25	21	17	14	12	10	8
	2–1	10001	68	52	41	33	26	21	17	13	11	8	7	5
	доля всех 2–строк	72	56	45	37	31	26	21	18	14	12	10	8
	3–0	7264	84	76	70	65	61	58	54	51	49	46	44	41
	3–1	6115	85	76	70	65	61	57	54	50	48	45	42	40
А	3–2	5076	84	75	69	64	59	55	51	48	45	43	40	38
	доля всех 3–строк	85	79	74	70	67	64	61	59	56	54	52	50
	4–0	5011	90	85	80	76	72	69	66	63	61	58	56	54
	4–1	4186	89	83	78	74	70	67	64	61	59	57	55	53
	4–2	3444	87	80	75	71	67	64	60	58	55	53	51	49
	4–3	2650	84	76	70	66	62	58	55	52	50	47	45	44
	доля всех 4–строк	90	86	83	81	79	77	75	74	72	71	69	68
	2–0 2–1	12165 10317	69 73	54 57	43 48	36 41	30 35	25 30	21 26	18 22	15 19	13 16	11 14	9 12
	доля всех 2–строк	73	58	47	39	34	29	25	22	19	16	14	12
	3–0 3–1 3–2	7459 6258 5026	83 86 87	76 80 80	71 76 75	66 72 70	62 68 66	59 65 63	55 62 60	53 59 57	50 56 54	48 54 52	46 52 50	44 50 47
Б
	доля всех 3–строк	88	83	79	75	72	70	67	65	63	61	59	57
	4–0 4–1 4–2 4–3	5153 4165 3275 2539	88 91 91 88	83 86 86 82	79 82 81 77	75 78 78 73	72 75 75 69	69 72 72 66	67 70 69 63	64 68 67 61	62 66 65 59	60 64 63 57	58 62 61 55	57 60 60 53
	доля всех 4–строк	93	90	87	85	83	81	80	78	77	76	74	73
	2–0 2–1	26245 21414	75 79	61 65	50 54	42 47	35 40	30 35	26 30	22 26	19 22	16 19	14 17	12 14
	доля всех 2–строк	79	65	55	47	40	35	30	27	23	20	17	15
	3–0 3–1 3–2	15860 12787 9542	90 91 88	84 86 82	79 82 78	75 79 74	71 75 71	68 72 68	65 70 66	62 67 63	60 65 61	58 63 59	55 61 57	53 59 55
В
	доля всех 3–строк	92	88	84	81	79	76	74	72	70	68	66	64
	4–0 4–1 4–2 4–3	10902 8271 5872 3983	94 93 95 93	90 90 91 89	87 87 88 85	84 84 85 82	82 82 83 79	79 80 80 76	77 78 78 73	75 76 76 71	73 75 74 69	72 73 72 67	70 72 70 65	69 70 68 63
	доля всех 4–строк	96	94	92	90	89	87	86	85	84	83	82	81
………………………………………………………………………………………………………..…..
	2–0 2–1	2107 1706	59 64	41 48	29 38	22 30	16 23	12 18	9 15	7 12	5 9	4 7	2 5	2 4
	доля всех 2–строк	67	50	38	31	25	21	17	14	12	9	7	6
	3–0 3–1 3–2	1277 1014 772	72 76 76	60 63 62	51 54 53	45 47 46	40 42 39	36 38 34	32 34 30	29 31 26	26 27 22	23 24 19	21 21 17	18 18 15
Ж
	доля всех 3–строк	83	74	68	63	58	54	50	47	44	42	39	37
	4–0 4–1 4–2 4–3	847 653 509 373	73 80 76 71	60 68 64 58	52 60 56 50	46 53 49 41	41 47 43 36	37 42 37 32	34 37 33 27	30 32 30 23	26 29 27 19	23 27 24 14	22 25 20 10	20 22 17 6
	доля всех 4–строк	89	82	76	72	68	64	61	59	56	54	52	50
……………………………………………………………………………………………………………
	2–0 2–1	91362 77056	63 75	51 62	42 52	35 45	30 38	26 33	22 29	19 25	17 22	14 19	12 16	10 14
	доля всех 2–строк	69	57	47	40	34	30	26	23	20	17	15	13
	3–0 3–1 3–2	56111 46537 37296	81 90 92	74 84 87	69 81 83	65 78 80	62 75 77	59 72 75	56 70 73	54 68 70	52 66 68	50 64 66	48 62 65	46 61 63
П
	доля всех 3–строк	89	84	81	78	75	72	70	68	66	64	63	61
	4–0 4–1 4–2 4–3	38445 31719 24475 17276	90 95 96 95	86 92 93 92	83 90 91 90	80 88 89 88	78 86 88 86	75 85 86 84	73 83 85 83	71 82 84 81	70 81 82 80	68 80 81 79	67 79 80 77	65 78 79 76
	доля всех 4–строк	95	93	91	90	88	87	86	85	84	83	82	81
Примечание: строки «доля всех l–строк» содержат данные о частоте первых l–строк среди всех l–строк, без учета их принадлежности l–k–наборам

Теперь мы можем получить верхнюю оценку той части символов в словах длиной не менее l, которую могли бы покрыть наиболее частые l–строки. С этой целью для каждой градации рангового распределения нужно выбрать значение, максимальное для данного l по всем l–k–наборам.