Я бы использовал список ребер, это 2 * n * sizeof(int) на слово из n букв. В качестве представления графа вполне годно(хотя перебор соседей будет сложным).

> Теперь собственно вопрос: нужно придумать такой формат/способ хранения графа, чтобы занимать как можно меньше памяти.

Вопрос в студию. А вообще, всё уже придумано до нас. Граф можно хранить в виде матрицы или же в виде вектора и связанных с ним списков. Второй способ компактнее.

Масив структур, где вместо ссылки, номер элемента.

З.Ы.: Учитывая, что весь словарь у тебя займет не такуж и много места, то лучше подумать о быстроте поиска/добавления слов. И проверь эффективность такого построения графа по сравнению с простым буквенным деревом на полном словоре.

> Граф можно хранить в виде матрицы

Учитывая, вершин сотни тысяч, это ни в какие ворота не лезет: 100000 * 100000 ~= 10 гигабайт

или же в виде вектора и связанных с ним списков

Так и храню, но все равно получается очень пухло (~ 10 мегабайт).

Если в списке ребер держать смещение до инцидентной вершины, то можно пытаться экономить на размере этого смещения. То есть упорядочить вершины так, чтобы большинство смещений можно было записать в 1 или в 2 байта. Но я не знаю, как вычислять (квази)оптимальный порядок. Да и в целом получается не слишком-то элегантно.

Вот и создал тему: вдруг у кого-то будут красивые идеи?

> Масив структур, где вместо ссылки, номер элемента.

Да, так и храню. Но получается пухло, нужно компактнее.

Учитывая, что весь словарь у тебя займет не такуж и много места, то лучше подумать о быстроте поиска/добавления слов

Добавлять слова не нужно, а графовая структура обеспечивает более чем достаточную скорость поиска/перебора. Проблема именно в занимаемой памяти, а не в быстродействии.

> Так и храню, но все равно получается очень пухло (~ 10 мегабайт).

Если в списке ребер держать смещение до инцидентной вершины, то можно пытаться экономить на размере этого смещения.

Ты уже сэкономил в 1000 раз, какой ещё экономии ты хочешь?

Добавлять слова не нужно, а графовая структура обеспечивает более чем достаточную скорость поиска/перебора. Проблема именно в занимаемой памяти, а не в быстродействии.

Если потребляет много памяти, сравни с буквенным деревом, может алгоритм построения графа не оптимален.

Какая структура используется? (Код в студию)

> Ты уже сэкономил в 1000 раз, какой ещё экономии ты хочешь?

Хочу, чтобы легко влезало в телефоны и прочие кофеварки, чтобы быстро скачивалось даже при плохом качестве связи. 10 Мб - очень жирно. Хочется уменьшить объем еще в несколько раз.

> Хочется уменьшить объем еще в несколько раз.

Словарь большой, пол-миллиона слов.

500k * 5 букв (7) = 2.5M (3.5M) Боюсь, нескольких раз тут явно не выйдет.

Если вспомните про разреженные матрицы, 10 мегабайт уже не будет. Правда, такое представлени эквивалентно списку ребер.

Экономия на размере смещения редко оказывается реально полезной. Все равно нужен бит под флаг, кроме того обращения по адресам, не кратным 4, неэффективны, ну и прочее.

Как строился граф? На приведенной картинке явно заметна некоторая оптимизация (экономия за счет совпадающих частей слов).

Если речь идет о передаче графа по сети, то можно 1) пройтись gzip-ом, 2) генерировать представление графа на стороне получателя.

> Если потребляет много памяти, сравни с буквенным деревом, может алгоритм построения графа не оптимален.

Если быть точным:
на одном словаре - в дереве 192013 вершин, в графе - 30150 вершин.
на другом словаре - в дереве 1841897 вершин, в графе - 235270 вершин.

Какая структура используется? (Код в студию)

Граф представлен как массив структур {буква, смещение}. Вершина - это непрерывный фрагмент массива. Первая ячейка внутри вершины - заголовок, остальные ячейки - ребра. Формат вершины такой:
{0, смещение-последнего-ребра-этой-вершины},
{буква-при-ребре-1, смещение-заголовка-вершины-на-конце-ребра-1},
{буква-при-ребре-2, смещение-заголовка-вершины-на-конце-ребра-2},
...,
{буква-при-ребре-N, смещение-заголовка-вершины-на-конце-ребра-N}

Я знаю, что такое представление не вполне оптимально. Но я не хочу улучать его по чуть-чуть, а надеюсь, что кто-нибудь предложить нечто элегантное/радикальное :)

> Если речь идет о передаче графа по сети, то можно 1) пройтись gzip-ом, 2) генерировать представление графа на стороне получателя.

Кроме передачи по сети, нужно, чтобы оно влезало в оперативную память кофеварки.

каждый узел как список пар (буква, адрес следующего узла). Список это на самом деле массив, оканчивающийся каким-нибудь специальным элементом типа (0, 0). В несжатом виде имхо это самый компактный способ. Если не устраивает - то хранить в сжатом виде, разжимая на лету.

>> Словарь большой, пол-миллиона слов.

500k * 5 букв (7) = 2.5M (3.5M) Боюсь, нескольких раз тут явно не выйдет.

Представление в виде графа экономит на одинаковых началах слов и на одинаковых окончаниях. Так что лучше думать не о размере исходного словаря, а о размере графа.

> Представление в виде графа экономит на одинаковых началах слов и на одинаковых окончаниях.

И тут же меняет эту экономию на представления в виде вершин, ребёр и направлений.

Так что лучше думать не о размере исходного словаря, а о размере графа.

Безусловно, это я в качестве иллюстрации.

Альтернативный способ хранения уже подсказали.

Ох, и раз уж погнались за точностью:

* на одном словаре - в дереве 192013 вершин, в графе - 30150 вершин, граф занял 566736 байт (буквы в utf-16)

* на другом словаре - в дереве 1841897 вершин, в графе - 235270 вершин, граф занял 3894792 байт (буквы в utf-16)

Дальнейшее удучшение зависит от задачи. Что кофеварка делает со словами?

Есть такая задумка:

begin    = 0
end      = 0
буква    - int
label(n) - n-ая метка, int
to(n)    - переход на n-ую метку, int
from(n)  - выход из n-ой метки, int

буквы, label(n), to(n) и from(n) отличаются друг от друга с помощью битовых масок.

begin -+- в --- е -+- д -+- р --- о -+- end 
       |           |     |           | 
       +- я -------/     |           | 
       |                 |           | 
       +- п --- е -+-----/           | 
       |           |                 | 
       |           \-----+- ч --- ь -/ 
       |                 | 
       \- р --- е -------/ 

Представляется как массив:

[
  ['в', 'е', label(1), 'д', label(2), 'р', 'о', label(3)],
  ['я', to(1)],
  ['п', 'е', label(4), to(2)],
  [from(4), label(5), 'ч', 'ь', to(3)],
  ['р', 'е', to(5)],
]

Тут мы храним все вершины, и все пересечения, но совсем не храним рёбер (кодируются в пересечениях).

> Дальнейшее удучшение зависит от задачи. Что кофеварка делает со словами?

Там всякие-разные алгоритмы ходят по орграфу. Это уже очень малькое отношение имеет к вопросу топика.

Впрочем, если интересно - см http://balda.sourceforge.net

Ох, и раз уж погнались за точностью:

* на одном словаре - в дереве 192013 вершин, в графе - 30150 вершин, граф занял 566736 байт (буквы в utf-16)

* на другом словаре - в дереве 1841897 вершин, в графе - 235270 вершин, граф занял 3894792 байт (буквы в utf-16)

Вполне прилично. Можно попробовать выбрать словарь по меньше или генерировать словоформы, но в последнем случае если твоя программа оптимально упаковала окончания слов в граф, то прироста не будет.

Интересный взгляд, спасибо.

> выбрать словарь по меньше

Это крайнее средство.

генерировать словоформы

Нужно представление именно в виде графа.

> пройтись gzip-ом

У нас информации о сжимаемых данных гораздо больше, чем у general purpose gzip-а. Например, мы знаем, что не важно, в каком порядке записаны ребра, исходящие из отдельно взятой вершины. Знаем, что не важно, какие вершины записаны раньше, а какие позже. Теоретически с использованием нашей дополнительной информации можно сжать словарь гораздо лучше, чем сжимает gzip.

Я бы предложил расширить алфавит двумя дополнительными значениями - «повторить» и «пропустить» и строить таблицу следующего вида:

begin -+- в --- е -+- д -+- р --- о -+- end  
       |                             |  
       +- я---- S --- R --- R --- R -|
       |                             |  
       +- п --- е --- S --- R --- R -|
       |                             |  
       +- R --- R --- S --- ч --- ь -|  
       |                             |
       \- р --- е --- S --- R --- R -|

S - пропусить
R - повторить

Будет избыточность по символам, но машем ручкой смещениям. Если избыточность будет достаточно велика, то появится смысл воспользоваться сжатием.

Достаточно радикально? ;)

(буквы в utf-16)

Не самый экономный способ хранить текст. В идеале (если выкинуть большие буквы, цифры и т.п.) можно перейти на последовательности битов, но в первом приближении достаточно перейти на байты.

Самое длинное слово ~ 15 символов. Средняя длина слова ~ 6 символов. Итого примерно пол-таблицы будет занято символом «пропустить».

Будет избыточность по символам, но машем ручкой смещениям. Если избыточность будет достаточно велика, то появится смысл воспользоваться сжатием.

Не получится, что кодирование повторяющегося символа «пропустить» съест места примерно столько же, сколько съедают смещения? ;)

Вполне может получится. Это надо замерять на реальных входных данных. Но в любом случае, один и тот же символ «пропуск» будет сжат на порядок лучше, чем разнообразные смещения.

«ведро», «ядро», «перо», «печь» и «речь»:

я.дро:ве*:пе.ро:*.чь:ре* - 24 байта

«Инвариант если вы пройдете вдоль линий слева направо от к обязательно получите какое-нибудь словарное слово»

инвариант:если:вы:пройдете:вдоль:линий:слева:направо:от:к:обязательно:получите:какое:нибудь:слов.арное:*о - 106 байт.

Хотелось бы узреть размеры графа в байтах для второго случая.

> Хотелось бы узреть размеры графа в байтах для второго случая.

1. Случай нетипичный. На практике словарь - это что-то вроде орфографического словаря. Там масса совпадающих префиксов и суффиксов. В приведенном случае - таких почти нет.

2. Вопрос топика в том и заключается: как бы минимизировать колчиство байт, потребное на запись заданного фиксированного графа?

Где-то сполгода назад тоже думал изобрести такую структуру, которая бы и произвольный граф(орграф) покрыла, и была бы в общем эффективнее (по памяти и по некоторым операциям) чем список ребер или матрица вершин.
Забил :)

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

Кстати мое глубокое имхо - граф словарю вреден. Рассмотри предельный случай - все слова языка описываются графом с 33+2 (+begin+end) вершинами.

(+)

>все слова языка описываются графом
Мож непонятно написал, исправляюсь: неориентированный граф К35 с петлями в каждой из 33-х символьных вершин.

пара соображений по оптимизации хранения графа :

- последовательные узлы объединять. В указанном примере «p--е» (те что снизу рисунка) должны образовать узел «ре»

- сводимые компоненты графа (подграфы) тоже объединять на основе регулярных выражений. В указанном примере должен появиться узел "(ве|я)д" (верхняя левая часть рисунка)

з.ы. максимально компактный в хранение формат как правило малопригоден для работы :)

> сводимые компоненты графа (подграфы) тоже объединять

Не очень понятно, что такое «сводимая компонента»? Это какой-то особенный подграф?

> Кстати мое глубокое имхо - граф словарю вреден.

Беда в том, что алгоритмам, которые пользуются словарем, удобен именно граф.

http://pco.iis.nsk.su/grapp/

Да как раз понятно - изоморфные преобразования графа предлагается делать, дабы уменьшить кол-во вершин.

Беда в том, что алгоритмам, которые пользуются словарем, удобен именно граф.

В каком-то смысле Вы правы: граф как дерево - очень удобен, как сеть - опять-таки мое вышеупомянутое имхо - нет. Хотя, с другой стороны, у Вас - вариация на тему K-дольного графа... Из этого знания вполне можно что-то выжать..

Например - ввести пул/хеш триграмм (троек букв): все возможные комбинации уложатся в 2 байтовое слово (правда, все 16 бит, зато используемых меньше, чем всех); триграмму в доле заменять на вершину с индексом в пуле триграмм - в вашем случае это вполне возможна экономия 2 ребер и вершин.
Как уже было указано - выносить изоморфные подграфы из долей в общую часть.. И тоже вести их пул, а в основном держать лишь ссылку на положение в пуле :)

Вот... навскидку,