Quatro: формат линейного представления графа

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

Связи хранятся в виде одного файла.
Файл содержит двоичные числа одинаковой разрядности.
Первое число - единица и одновременно является идентификатором первого узла. Это обстоятельство позволяет легко определить разрядность остальных чисел.
Файл не может содержать болше чисел, чем значение самого большого из них.
Признак идентификатора узла - нечётное число равное своему порядковому номеру в файле.
Признак связи - нечётное число отличное от своего порядкового номера в файле. Это число равно одному из имеющихся в файле идентификаторов узлов.
В узле без связей сразу после идентификатора записан ноль.
В узле со связями сразу после идентификатора следует число с порядковым номером связи в файле.
В последней связи узла сразу после идентификатора другого узла записан ноль.
В прочих связях узла после идентификатора другого узла записан порядковый номер следующей связи.
На месте удалённой связи записываются два числа со значением ноль. Предыдущая связь переключается на следующую за удалённой.


Значения хранятся в отдельных файлах. В качестве имени файла берётся идентификатор соответствующего узла.

Идентификатор узла определяется по хэшу значения.

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

Гонки

Старт

Здесь шумно. У линии старта толпятся болельщики. В воздухе запах жжёной резины. Покрышки моего автомобиля ещё горячие. Скоро начнётся второй заезд. Он определит победителя соревнований.

Уверен, что победа достанется мне. Почему я в этом уверен? Кто я такой? Я такой же гонщик, как и ты. Выгляни из окна. Мой жёлтый скоростной болид стоит слева от твоего автомобиля. Смотри, я машу тебе рукой.

Заметил, какой необычный корпус у моей машины? Обтекаемая форма позволяет мне нестись по трассе быстрее пули. Тебе будет трудно меня обогнать. Лучше закрой книгу и иди домой, посмотри мультики.

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

Школа гонщиков

Добро пожаловать в нашу школу. Я твой учитель. Мой предмет называется "подготовить гонщика". Почему тебе это название кажется странным? Название как название.

Я обучу тебя приёмам экстремального вождения автомобиля. Ты спрашиваешь, как меня зовут? Тебе знать этого не положено. Гонщики не должны знать, кто их обучил. Меньше знаешь -- быстрее едешь! Всё равно, когда ты покинешь здание школы, ты сразу забудешь о её существовании.

Главное запомни, что я тебе сейчас скажу: "В игре есть машины и на них можно ехать быстро или медленно." Почему ты говоришь, что это чепуха. Это не чепуха. Лучше запиши себе в тетрадь, чтобы не забыть. Записал? Молодец, что записал. Теперь ты настоящий гонщик и можешь принять участие в соревнованиях.

Не веришь? Хорошо. Вот тебе учебный автомобиль. У него на двери кнопка. Читай, что на ней написано. Да, верно. Написано: "посадить гонщика". Жми, не бойся.

Так, теперь ты сидишь за рулём. Нет, руль вертеть не нужно. Это за тебя сделает компьютер. Да, согласен, это круче, чем коробка-автомат. Чтобы ехать быстро, жми на кнопку с надпистью "ехать быстро". Чтобы ехать медленно, жми на кнопку рядом. На ней так и написано: "ехать медленно".

Не буду спорить с тобой. Это и правда проще простого. По прямому участку трассы ты едешь быстро. На крутом вираже сбавляешь скорость и едешь медленно.

Ты спрашиваешь, где кнопка с надписью "остановиться"? Её нет. Это же спортивный автомобиль. Не беспокойся, в конце трассы компьютер остановит его автоматически. Ну, прощай! В добрый путь! Пока! Успехов!

Нет, отвечать на другие вопросы я не могу. У меня мало времени. Нужно успеть подготовить других гонщиков, а до началагонки осталось меньше секунды.

Ответы на вопросы

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

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

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

Прочитав эту книгу, ты узнаешь из каких частей состоит программа и сможешь сам начать программировать. А начинать нужно с самого интересного. С программирования гоночной машины!

Гоночная машина

Сетевая база в одном файле 2

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

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

Сетевая база в одном файле

Размышляя над системой, написанной на PHP, пришёл к пониманию того, что лежащую в основе графовую базу данных нужно переработать. Порядок привязанных узлов нужно отслеживать на уровне базы данных. Желательно сократить список технологий, задействованных при реализации базы данных, и максимально всё упростить. В идеале описать формальные требования. Чем и займусь.

1. Записи не удаляются.
2. Связи могут только добавляться.
3. Связи имеют направление.
4. Одному строковому значению соответствует один узел.
5. У всех узлов есть значение - NULL или хэш строки.
6. Хранятся только цепочки связей.
7. Звено ценпи состоит из порядкового номера звена, номера следующего звена и ссылки на звено-узел.
8. Порядковый номер звена соответствует его расположению в файле.
9. Узел - это первое звено в цепочке, которое не указывает на другие узлы.
10. При каждом запросе узла, создаётся новый объект.

Пример: узел 3 связан с узлами 1 и 2.

address    next    link    комментарий
1          0       1       узел 1
2          0       2       узел 2
3          4       5       узел 3 (последнее звено 5)
4          5       1       связь узла 3 с узлом 1
5          0       2       связь узла 3 с узлом 2 (последняя в цепи)
6          0       6       узел 6

Поскольку приложение, использующее базу данных, отслеживает тип узла, нет необходимости помечать узлы, привязанные к значениям. Функция node.hasValue() не нужна.

Компьютерная лингвистика, так сказать...

Попытался между делом написать код на PHP под правила языка, описанные в одной из предыдущих статей.

Работа ещё не завершена, но что-то уже прорисовывается. Можно нащупать проблемные места и сделать доработки. Код выложен на GitHub.

Код разделён на две части: сетевая (графовая) база данных и правила синтаксиса. Называются, соответственно, - graph и syntax.

Сетевая база предоставлет средства для извлечения и изменения связей узлов, а также позволяет прикреплять к узлам некоторый набор данных. После нескольких мучительных дней терзаний понял, что этот набор данных является значимой сущностью на более высоких слоях абстракции. Представление его в виде объекта с интерфейсом приводило к усложнению кода. Сначала было два варанта строка для хранения слов и строка для хранения ссылок на файл. (Да-да... Члены предложения могут быть и файлами. И кусками кода, если уж на то пошло.) И эти два интерфейса стали расползаться из глубин хранилища наверх до самого ГУЯ. Вобщем, теперь у узла может быть два значения NULL или строка. Интерпретация строки выполняется за пределами хранилища. Файл можно хранить в виде JSON-чика, в котором указан тип данных и ссылка или путь к файлу. Данные привязываются к узлу в момент создания и не могут быть изменены. По хэшу строки всегда можно найти, привязанный к ней узел. Узлы не удаляются. Причина тому в том, что свзи в базе однонаправленные, и для удаления некоторых узлов пришлось бы долго обходить, возможно, миллионы имеющихся узлов. Ради упрощения и ускорения действует принцип - слово не воробей, вылетит не поймаешь. На самом низком уровне связи хранятся в виде папок и ссылок файловой системы. Простенькие штучки на бесплатном сервере Cloud9 занимают где-то 0,1 секунды. Не плохо бы попробовать замерить на SSD и на машинке помощнее. На нижнем уровне хранилища можно будет задействовать Redis или подключиться к другой базе. Была идея выложить эти папочки со связями узлов в открытый доступ, чтобы можно было скармливать внешним системам как статику.

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

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

complimnet
Член предложения (кроме сказуемого). Привязывается через валентность к сказуемому и вопросам от него.

argument
Валентность сказуемого. Связывает сказуемое с вопросами, которые можно от него задать.

predicate
Сказуемое. Связано через валентность с вопросительными словами и всевозможными ответами на них в разных предложениях. Буквы сказуемого хранятся в специализированных узлах - словах.

question
Вопросительное слово. Берёт на себя функции падежных окончаний и много ещё чего, поскольку употребляем по новым правилам только начальные формы слов. Вопрос связан с ответом через валентнось и второстепенный член предложения. Буквы, как и в случае со сказуемым, содержаться в узлах-словах.

answer
Ответ.

word
Слово. Одно и то же слово может содержать ссылку на сказуемое, вопрос и ответ. В английском, например, одно и тоже слово может обозначать как действие, так и предмет. Или ещё для такого случая: "важно не сколько, а как".

Отсутствуют пока что узлы типа reference, которые позволят в качестве ответов использовать подчинённые предложения.

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

Схема связей такова:

Private money: подходы

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

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

Что будет с торговлей? Поставщик товара может узнать, кому и по какой цене он был продан. Он сможет в обход посредника связаться с покупателем сам. Да, частные деньги не способствуют созданию длинных цепочек купли-продажи. С их помощью трудно надувать финансовые пузыри. Они хороши только для тех кто создаёт и тех кто пользуется плодами этого труда. Поэтому деньги и называются частными. Зачем частному лицу поддерживать систему, которая нацелена на его ограбление и обирание? Незачем.

Частные деньги

Российское общество плавно, но неотвратимо погружается в пучины мирового финансового кризиса. Люди остаются без работы и средств к существованию. Как это возможно, мне не удаётся понять уже много лет. Как может существовать безработица? Что на планете Земля уже построен рай? Всё сделано, все потребности удовлетворены? Какая магия заставляет людей бездейстововать?

Простой пример. Нет работы? Построй дом. Жильё нужно всем. Однако никто этого делать не будет. Нужны права на землю, нужны материалы. Выход простой. Идём в банк, берём кредит, покупаем всё что нужно, строим, продаём, возвращаем кредит банку с процентами. Живём и радуемся.

Либо другой вариант. Идём в банк, узнаём, какой с нас хотят получить процент, считаем, уходим из банка недовольные. Есть правда ещё вариант. Банк сразу откажет в кредите, потому что у вас нет работы. Круг замыкается. Работы завтра не будет, потому что её нет сейчас. Разве не логично? Разве вы не готовы так думать постоянно? Дождь не пойдёт завтра, потому что он не идёт сегодня.

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

Спросим себя далее, а откуда деньги у банка. Всем известно, что банк привлекает деньги под меньший процент и раздаёт их под больший. На разнице процентов худо-бедно и живёт. Попутно распределяет средства вкладчиков по наиболее выгодным и наименее рискованным проектам. Наш проект постройки дома оказался либо недостаточно выгодным, либо слишком рискованным. Хороший банк защитил вкладчиков.

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

Мне правда пока не понятно. Мы ведь собирались строить дом. В доме будут жить люди. Причём здесь какие-то вкладчики и их банки? За что мы должны им платить деньги? За то, что они дали нам попользоваться своими деньгами? Это как умереть с голоду, сидя перед тарелкой с кашей, потому что никто не дал попользоваться своей ложкой.

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

Современные информационные системы собирают и хранят огромные объёмы информации. Им вполне по силам учесть все сделки, совершаемые жителями планеты. Не верите? Бухгалтерия вашей организации хранится на компьютере. Фискальная информация государств хранится тоже на компьютерах. В них же записана маркетинговая информация о том, на каком сайте какая ссылка была вами нажата и масса всякого другого хлама. Думаю, что проходя с чипизированным паспортом в сумке через рамку на входе метрополитена, мы шлём привет в один из ЦОДов. То есть технические возможности на текущий момент многократно превосходят уровень, необходимый для введения частных денег. Парка персональных компьютеров и смартфонов будет более чем достаточно для внедрения системы частных электронных денег. В чём её суть?

 Похоже на векселя. За стройматериалы мы расплачиваемся длинным уникальным номером. Платим числом. Уже круто, не правда ли? Этот номер мы только-что придумали и зарегистрировали в системе. Номер этой купюры, привязан к нашему личному идентификатору в системе и к информации о приобретённом товаре. Общую классификацию товаров создать сложно, но тем не менее возможно. Номер купюры также привязан к личному идентификатору продавца.

Продавец при закупке следующей партии стройматериалов использует вашу купюру или создаст собственную. История всех сделок в которых участвовала купюра сохраняется и доступна каждому, кто ей владеет. У каждого эмитента будет свой рейтинг в системе. Основная идея состоит в том, чтобы привязать платёжное средство к фактической хозяйственной деятельности.

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