Переносы по алгоритму TeX

[JAW]

Вот здесь:
http://nedbatchelder.com/code/modules/hyphenate.html

Я нашел, вероятно, относительно простую для понимания реализацию алгоритма переносов Frank Liang'а реализованную в системе TeX.

Реализация на Python с фиксированным набором патернов.

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

Брежу этой идеей давно. Эти алгоритмы бесплатные, наборы патернов переносов также открыты и редактируемы. НО НИКТО ИХ НЕ РЕАЛИЗУЕТ.

Проблема в том, что я уже "кастрированный" программист. Все забыл.
Может посмотрите?

Вторая проблема... В TeX (а он написан на нечто типа Паскаля) Кнут разбил все это дело на две части. Первая часть, это генерация структуры для быстрого поиска по ней, которая записывается уже в виде структуры.
Сам переносчик подгружает эту структуру и уже по ней работает.

Вот, честно говоря, в современных компьютерах может это и не особо критично, но реализовать бы Кнутовский алгоритм.
Однако... Исходники документированы прекрасно, но DEC, это хакер старой закалки. Там не смотря на документацию нефига не просечь.
Он явно строит дерево, но дерево на массивах и постоянно ссылается на алгоритмы рассмотренные в "Искусстве программирования".

P.S. Исходный пакет документации и то, что писал по этому поводу Кнут могу попробовать поискать..., Даже на русском.

 

[AirGraph]

Ответ: Переносы по алгоритму TeX

dll плохо тем, что не будет канать в Mac OS X, например. IMHO, если начинать такой проект, то можно попытаться реализовать это дело в виде библиотеки скриптов на JavaScript. Я лично готов участвовать в команде БЕЗВОЗМЕЗДНО, т.е. ДАРОМ. ;-)))) Мне лично интересно программить алгоритм, я заберу описание к нему и посмотрю, но одному мне не потянуть такой проект. Надо собирать команду, поделить задачу на куски, прописать ТЗ на функции в виде: входные данные->алгоритм->выходные данные и при этом кто-то должен рулить командой отлично понимая как это все будет выглядеть в результате. Работать оно должно абсолютно универсально, на любой платформе и с любым софтом. Интерфейс к InDesign или к чему-то еще - дело последнее. И еще, как я понимаю, результат, как и в любом проекте OpenSource, должен быть абсолютно бесплатным и доступным всем. Предлагаю всем кто интересуется этим делом высказаться на этот счет.

AirGraph.

 

[JAW]

Ответ: Переносы по алгоритму TeX

AirGraph
На самом то деле DLL не цель...
Предполагается, что нужно получить линкуемую универсальную библиотеку (OpenSource).
Если посмотришь тот алгоритм на Питоне, то поймешь, что он влезает в страничку распечатки, т.е. алгоритм довольно тривиален, другой момент, что на Питоне строятся списки, а в их оптимальности у меня есть довольно большие сомнения.

Исходный код на Паскале. Вернее на нечто называемом WEB, некая технология объединяющая програмный код и документацию.
Если обработать этот WEB системой TeX, то получим некую книгу, которая называется TeX Programmers Guide, кажется.
Если обработаем другим транслятором, то получим нечитаемый програмный код на Паскале, третьим - нечитаемый програмный код на C.

P.S. Насколько понимаю есть переработанный код на Java. Нужно поискать, может он читабелен и это весь TeX, а не только алгоритм переносов.

P.P.S. Да, забыл добавить, что OpenOffice использует именно TeX'й алгоритм, вернее TeX'е патерны. Какой именно набор патернов в OO в комплекте, честное слово не уверен, может и далеко не лучший.

Да... В принципе существует программа PatGen, которая из словаря переносов генерирует набор патернов, т.е. если есть словарь переносов, то можно его того... Прихватизировать, короче

Нашел я скан искодной статьи Фрэнка Лиянга. Естественно на английском.
В общем дальнейшее завтра, если работа не накроет.

 

[AirGraph]

Ответ: Переносы по алгоритму TeX

Код на С - это самое для меня понятное, если нет книжки с описанием самого алгоритма построения дерева переносов и исключений. Я посмотрел это PhD, все классно, разобраться можно, но небыстро... ;-) А еще ты упоминал про исходники, которые классно документированы. Где? А DEC - это к PDP 1140 имеет отношение, если да - то это то что надо!

AirGraph.

 

[Strizh]

Ответ: Переносы по алгоритму TeX

dll плохо тем, что не будет канать в Mac OS X, например. IMHO, если начинать такой проект, то можно попытаться реализовать это дело в виде библиотеки скриптов на JavaScript. AirGraph.

Имхо, JavaScript не выход. Из одних и тех же Си/С++ сырцов можно собрать dll на PC и dylib/bundle на Mac. будет небольшой (очень маленький) платформозавищий кусок. У меня есть в этом приличный опыт. Так что если соберетесь что-то писать/переписывать, то и мне сообщите.

 

[AirGraph]

Ответ: Переносы по алгоритму TeX

Про JavaScript я в порядке обсуждения. На нем мы вовсе не зависим от платформы и, кстати, от лицензии на компиляторы. На маке это дело free не знаю как на PC. Но сам я с удовольствием вспомнил бы про давно забытое программирование на С/С++ в такой компании. ;-) Возможно, сначала надо продумать архитектуру проекта и уж потом браться за выбор конкретных инструментов.

AirGraph.

 

[JAW]

Ответ: Переносы по алгоритму TeX

AirGraph

А DEC - это к PDP 1140 имеет отношение, если да - то это то что надо!

DEC, это Дональд Эрнстович Кнут
Просто он так свои комментарии подписывает

Это автор монстройдного 3-х томника искусство программирования, и системы TeX, которую он начал писать после того, как увидел то ублюдство, которое получилось из очередного переиздания книги в результате набора на аналоговых фотонаборах (это те, которые буковки проецировали). А там как раз первые лазерные принтеры (эксперементальные) и первые цифровые фотонаборы подоспели.

 

[JAW]

Ответ: Переносы по алгоритму TeX

Нашел свое старое описание алгоритма переноса (к сожалению не реализации) из The TeX Book.

И в этом же архиве несколько реализаций на C и Питоне

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

 

[AirGraph]

Ответ: Переносы по алгоритму TeX

Я сильно заблуждался в плане ясности текста на С... ;-))))) Там под 1000 строк кода и разобраться что к чему не представляется возможным. Посему, думаю, надо подковываться в теории с самогог начала. А есть еще какая-нибудь макулатура, кроме PhD, на тему алгоритмов формирования дерева переносов и исключений по заданному словарю переносов и алгоритмов обработки слов текста по созданному дереву? Лично мне, если участвовать в этом проекте, придется начинать от печки.... ;-)

AirGraph.

 

[Strizh]

Ответ: Переносы по алгоритму TeX

Я сильно заблуждался в плане ясности текста на С... ;-))))) Там под 1000 строк кода и разобраться что к чему не представляется возможным. AirGraph.

Там то все ковырять и не нужно. Есть несколько методов, которые возвращают слово с переносами. остальное реализация, которая тебе не нужна.
На выходных попробую посмотреть что и как.

 

[JAW]

Ответ: Переносы по алгоритму TeX

AirGraph
За переносы отвечает, кажется, только hyphen.c
Остальное, это более глобальная библиотека вообще для выключки строк.

Или посмотри Питоновскую библиотеку, там только этот модуль переносов и обвязка.

P.S. Я еще PatGen накопал - генератор патернов переносов из словаря.
Пытаюсь натравить его на Баховский словарь Пока безрезультатно, возвращает какую-то ошибку.

 

[Strizh]

Ответ: Переносы по алгоритму TeX

Поигрался я немного. Слегка подправил сишный код и вот что имеем:

Ре-фриже-ра-тор
Баш-корто-стан
грампла-стин-ка
произ-вод-ство
экс-ги-би-ци-о-нист

Есть смысл продолжать?

 

[Specialist]

Ответ: Переносы по алгоритму TeX

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

 

[@diz@]

Ответ: Переносы по алгоритму TeX

Ну в плане разделения на слоги это все абсолютно логично

фриже
корто
грампла
произ

Не очень понятно: по какому критерию это не разбивается.

 

[AirGraph]

Ответ: Переносы по алгоритму TeX

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

AirGraph.

 

[Specialist]

Ответ: Переносы по алгоритму TeX

фриже
корто
грампла
произ

Не очень понятно: по какому критерию это не разбивается.

Может это попытка анализа морфем? "фриже" это корень и его дробить нежелательно.

 

[JAW]

Ответ: Переносы по алгоритму TeX

Так...
Я положил в архив всего один набор патернов.
Повторю, их более пяти и стоит еще поискать, т.к. дело было давно и не факт, что это последня и лучшая версия.

Кроме того... Нужно понимать, что патерны редактиуются (правила можно расширять). Есть программа генерирующая эти патерны по словарю переносов (поищите patgen). И, что самое важное... Оптимизация патернов должна обеспечить возврат допустимых точек переноса. То, что возвращаются не все точки не страшно. Важно, чтобы не возвращались недопустимые.

 

[Flame]

Ответ: Переносы по алгоритму TeX

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

Категорически не согласен )) Возвращение не всех точек переноса dramatically усложняет хорошую выключку.


Не по теме:
Вообще у меня есть легкое подозрение, что фетишизация качества работы кнутовского алгоритма сродни стариковскому "раньше небо было голубее, и девушки моложе"

 

[Strizh]

Ответ: Переносы по алгоритму TeX

Помощники нужны, Strizh? Может и я на что сгожусь? ;-) Меня, правда, накроет работой на неделю, но потом я должен быть относительно свободен.AirGraph.

Ну это я так, часик выделил и поигрался. Код написан был в 2001 году (по дате файла) есть кое-какие косяки, их нужно с умом поправить. Так что милости просим.

 

[JAW]

Ответ: Переносы по алгоритму TeX

Категорически не согласен )) Возвращение не всех точек переноса dramatically усложняет хорошую выключку.

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

Я очень рекомендую почитать внимательно тот текст, который я выдрал из "Все про TeX".

Нужно понимать, что переносы делаются не по алгоритму, а по словарю.
Американский изначальный словарь (набор патернов) был построен на основании словаря переносов. Потом он был минимизирован (компромис, т.к. компьютеры были маленькие) но и несмотря на минимизацию возвращал, не помню цифру, но более 90% точек переноса.

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

НО!!!! ЧТО САМОЕ ВАЖНОЕ!!!
Набор патернов РЕДАКТИРУЕМ и ОТКРЫТ.
В частности те 4 ошибки правятся 4-мя строчками в словаре и эти строчки очевидны любому, кто почитает описание алгоритма.