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

  • Автор темы Автор темы JAW
  • Дата начала Дата начала
Статус
Закрыто для дальнейших ответов.
Ответ: Переносы по алгоритму TeX

JAW сказал(а):
Ну а что я? Я плагин по любому писать не буду...
Нажмите, чтобы раскрыть...
Стукни мне в аську или в gtalk. opatgen я сегодня собрал.
В форуме общаться неудобно. Ну или в крайнем случае в мыло пиши

icq: 55006453
gtalk job4job гаф gmail.com
мыло то же
 
Ответ: Переносы по алгоритму TeX

D:\Development\_src\opatgen\Debug>opatgen.exe --help
This is OPATGEN, version 1.0
Usage: opatgen [-u8] DICTIONARY PATTERNS OUTPUT TRANSLATE
Generate the OUTPUT hyphenation file from the
DICTIONARY, PATTERNS, and TRANSLATE files.

-u8 files are in UTF-8 UNICODE encoding.
Нажмите, чтобы раскрыть...

А нашел бы кто форматы входных файлов - было бы вообще замечательно.
 
Ответ: Переносы по алгоритму TeX

Все лежит на зеркалах CTAN
http://www.ctan.org и оттуда на зеркальные FTP сервера.
Извини, но сейчас у меня выходные ;)
С Рождеством, однако ;)

Да... С Patgen не все так просто однако, на работе лежит откомпилированная документация, но это до 9-го...
 
Ответ: Переносы по алгоритму TeX

Пипец, типа это МНЕ надо!
 
Ответ: Переносы по алгоритму TeX

А мне это тоже не надо ;)
Я вёрсткой уже давно чисто для развлекухи балуюсь...

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

P.S. Всё необходимое для понимания работы базового алгоритма я здесь выкладывал в теме.
Дополнительные материалы по PatGen и т.п. ну серьезно только с работы и еще фиг знает сколько подумать, чтобы нормально сформулировать.

Поищи по ключевым словам, opatgen, patgen +TeX
Я тут ссыли давал, но на английском... На русском ничего нет.
 
Ответ: Переносы по алгоритму TeX

Все, о чем здесь упоминалось, давно скомпилено и работает в виде отдельных программ.
 
Ответ: Переносы по алгоритму TeX

Так а что еще нужно?
 
Ответ: Переносы по алгоритму TeX

JAW сказал(а):
Так а что еще нужно?
Нажмите, чтобы раскрыть...
Мне, собственно говоря, ничего не нужно, так как более 2 лет не занимаюсь версткой и больше года вообще не занимаюсь полиграфией.
Топикстартер был не я - я просто вызвался помочь. Но если у вас, уважаемый JAW нет времени на ваши же желания, то я умываю руки.
Удачи.
 
Ответ: Переносы по алгоритму TeX

Максим!!!

Чтобы было понятно... Мне ЛИЧНО НИЧЕГО НЕ НУЖНО!!!
У меня есть только та информация на которую я дал ссылки в теме.

Однако мне было бы интересно видеть реализацию алгоритмов переносов TeX в популярных системах верстки.

Данный топик, честно говоря, возник в противовес с треплом Батова о его гениальности. Мне было бы интересно протестировать его алгоритм по сравнению с OpenSource алгоритмами и доказать, что есть алгоритмы не на много худшие.
 
Ответ: Переносы по алгоритму TeX

ну, положим, чтобы протестировать алгоритм, его совершенно необязательно куда-то прикручивать, достаточно дать ему на вход слово и посмотреть какие он переносы расставит. и как я понял, Максим уже добился определенных результатов в этом плане.
 
Ответ: Переносы по алгоритму TeX

Прочитал тему. Интересно. Разрешите, расскажу о своём опыте в этом деле.
  • 30 минут мне потребовалось, чтобы найти диссертацию Франка Лянга в сети.
  • 3 часа потребовалось, чтобы прочесть и понять её полностью.
  • 10 часов потребовалось, чтобы написать программу, генерирующую древовидную структуру («Packed trie») по паттернам.
  • 3 часа потребовалось, чтобы написать программу расстановки переносов по древовидной структуре.
  • 3 дня я собирал вместе и исправлял паттерны, чтобы добиться хороших переносов, потом мне надоело, т.к. я понял, что это тупиковый путь.
  • 10 часов мне потребовалось, чтобы написать программу генерации паттернов по словарю (аналог PatGen). Исправляя словарь (и перегенерируя паттерны), мы получаем гораздо лучший результат, чем исправляя сами паттерны.
  • Через пару часов тестирования я понял, что по одному и тому же словарю переносов можно сгенерировать паттерны, обладающие разной ПРЕДСКАЗАТЕЛЬНОЙ СИЛОЙ. Т.е. паттерны позволяют расставлять переносы не только в словах из словаря, но и угадывать правильное расположение переносов в других словах. Несложно доказать, что таблица с минимальным количеством паттернов, правильно обрабатывающая словарь, обладает максимальной предсказательной силой.
  • 3 часа исправлял программу генерации паттернов, чтобы выдавать минимальное количество паттернов. Вместо 10 секунд программа проработала ночь.
  • 3 часа потребовалось, чтобы всё это переписать на PHP.
    Вот результат: http://iproc.ru/?page_id=10
Итого примерно 5 дней.

Объём исходника, работающего на сайте, составляет всего около 10 экранных страниц. Из них 3 страницы кода и 7 страниц занимает закодированная древовидная структура.

Сейчас осознал, что ключевым промахом Франка Лянга является то, что он все буквы трактует отдельно, а не вводит классы букв (напр., гласные, согласные, твёрдый и мягкий знак...). Сейчас работаю над продвинутой версией алгоритма, оперирующего с классами, а не с буквами. Такой подход должен ещё раза в 2-3 уменьшить объём паттернов, и тем самым улучшить их качество. Недостаток: паттерны с классами уже не будут совместимы с системами TeX.

На обычном компьютере время генерации паттернов с разбиением на классы составит примерно год. Благо, есть доступ к вычислительным кластерам Таганрогского технологического института и Московского физико-технического института. Эти системы одни из самых мощных в России.

После этого полный расстановщик переносов русского языка будет занимать всего около 5 экранных страниц, с комментариями. Вот именно эту конечную версию собираюсь выложить в виде Open Source. Жаль только, сейчас прижали с диссертацией, поэтому вернуться к проекту удастся лишь месяца через 3 :(

А пока было бы приятно услышать отзывы. Ссылка была дана выше.
 
Ответ: Переносы по алгоритму TeX

проверил на нескольких заковыристых словах - полет нормальный :up:
 
Ответ: Переносы по алгоритму TeX

SAnton
Есть ещё один Жирный недостаток.
Алгоритм Франка Лянга практически универсален.
Разбиение патернов на классы снизит его универсальность.

Сила алгоритма TeX скорее в многообразии поддерживаемых языков и баз патернов. Причём эти базы общедоступны.

Кстати... Добавление собственных алгоритмов переноса в TeX по сути не вполне закрыта. Если создать соответствующий патч к TeX, чтобы он смог воспринимать "продвинутую базу переносов" и сделать его универсальным, то это вполне нормально. Я думаю, что вполне реально списаться со своими идеями с Дональдом Кнутом. Правда вот с мылом проблемы... Но, думаю, найти будет не очень трудно.
 
Ответ: Переносы по алгоритму TeX

И напомню ещё одну очень ЖИРНУЮ неприятность.
Словаря переносов русского языка до недавнего времени не существовало.
Не скажу как сейчас, давно не следил за этой темой.

В отличие от словаря, например, английского языка.

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

Думаю, что стоит остановиться на достигнутом... 7 страниц против 5...
А это того стоит? Я конечно понимаю, что стоит проверить свои алгоритмы, но не дороговата ли цена?
 
Ответ: Переносы по алгоритму TeX

К модераторам...
Просьба закрепить эту тему, чтобы опять не уплыла.
 
Ответ: Переносы по алгоритму TeX

Да.

Самая большая проблема*— это отсутствие качественного словаря переносов. Т.к. все манипуляции так или иначе опираются на словарь. (Пусть даже в нём будет не так много слов, но зато там будут правильные переносы).

Предлагаю взять список слов русского языка (со словоформами), и к нему применить два принципиально разных алгоритма:
1) алгоритм Игоря Батова;
2) алгоритм Франка Лянга с моими паттернами.
И затем вручную «разрулить» все несовпадающие варианты переносов. Это, конечно, не отрицает возможности того, что на каком-то слове алгоритмы ошибутся одновременно, но, я думаю, это маловероятно, т.к. алгоритмы разные и к расстановке слов подходят «с разных сторон».
 
Ответ: Переносы по алгоритму TeX

По поводу классов: даже самая банальная «звёздочка» (*), обозначающая «любую букву», уже очень помогла бы.

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

.пе1ре3*4

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

---------------------------------------------

Если интересно, расскажу вкратце, что такое паттерны. Они выглядят примерно так:

4ст. 2вм 1вме 2в1н 2вля вно1 в3ну. 4в3на
в2нес су3кн би3тва ло3вки ас3сны детс3ки
.шу5мны ско1ль3з де3р3зки родс3т1в

Точка обозначает начало или конец слова. Нечётные цифры обозначают возможность переноса, чётные — невозможность. Причём бо́льшие цифры «важнее». Цифры можно трактовать так:
1 — правило переноса
2 — исключение из правила
3 — исключение из исключения из правила
и т.д. Кроме того, если буквы одного подходящего паттерна являются началом букв другого подходящего паттерна, то паттерн меньшей длины игнорируется.

Паттерны упаковываются в дерево, и по нему (а также по рассматриваемому слову) бегает конечный автомат. Быстродействие не зависит от количества паттернов, но зависит (почти квадратично) от длины слова. (К сожалению, для анализа звёздочки в паттернах уже потребуется автомат с несколькими состояниями.)

Легко заметить, что такой подход срабатывает для большинства языков. (Изначально был разработан для английского)

---------------------------------------------

Паттерны генерируются по словарю, причём их можно сгенерировать как угодно. Самый банальный вариант — для каждого слова в словаре (например «Антон») генерировать соответствующий паттерн (например «.ан1тон.»). Тогда получаем просто переносы по словарю, и ни одно слово, не входящее в словарь, не сможет быть перенесено (например «четырёхсотвосьмидесятимиллиграммовый»). Интереснее всё же написать ТАКОЙ генератор паттернов, который бы генерировал по словарю как можно более качественные паттерны, чтобы они справлялись с новыми словами.
 
Ответ: Переносы по алгоритму TeX

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

Просто в списке обнаружил брак: «2вм» всегда подавляет «1вме». Буду исправлять прогу... :(((
 
Ответ: Переносы по алгоритму TeX

Антон, добрый день!
SAnton сказал(а):
...алгоритмы разные и к расстановке слов подходят «с разных сторон».
Нажмите, чтобы раскрыть...
Посмотрел я диссертацию Ф. Лянга. На мой взгляд, философия batov's hyphenator и философия подхода Ф. Лянга совпадают абсолютно. Различие возникает лишь на этапе реализации. Не знаю, насколько это правомерно, но я бы провел аналогию с философией, реализованной в PS и PCL принтерах. Все определяется соотношением код/данные.

У Лянга, поправьте меня, если я ошибаюсь, реализована "PCL-модель": информативная часть содержится в данных (паттернах).

Batov's Hyphenator реализует "PS-модель": содержательная часть помещена в код... Например, то, что Вы называете классами, реализовано в batov's hyphenator под названием "шаблон". Получается что-то вроде такого: "если за любым символом следуе две гласных, делать то-то..." (Если, конечно, я правильно интерпретирую Вашу терминологию.)

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

Но, почему-то меня не покидает ощущение, что "PS-модель", теряя в универсальности, для каждого отдельного языка дает лучший результат... Этот подход более гибкий... И в первую очередь именно за счет применения шаблонов...
 
Статус
Закрыто для дальнейших ответов.
Верх Низ