Про переносы Hunspell

[Skvoznyak]

HunSpell. Используются патерны Лянге, оно же используется в TeX, OpenOffice, AdobeMobileSDK, InDesign.

При использовании движка быть осторожным и читать Readmy. Adobe и в OO не читали и накосячили... Требуется конвертация патернов переносов, программка идёт в комплекте.

Можно поподробнее, где эта программка?

 

[JAW]

Ответ: MS Office какую версию купить? Или поставить Open Office?

Можно поподробнее, где эта программка?

Ну, переносы:
http://sourceforge.net/projects/hunspell/files/Hyphen/2.8/
Там в архиве substrings.c

//
// A utility for finding substring embeddings in patterns

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXPATHS (256*1024)

//
//
static void die(
  const char*msg
) {
  fprintf(stderr,"%s\n",msg);
  exit(1);
}


// Finds the index of an entry, only used on xxx_key arrays
// Caveat: the table has to be sorted
static int find_in(
  char *tab[],
  int max,
  const char *pat
) {
  int left=0, right=max-1;
  while (left <= right) {
    int mid = ((right-left)/2)+left;
    int v   = strcmp(pat,tab[mid]);
    if (v>0) {
      left = mid + 1;
    } else if (v<0) {
      right = mid -1;
    } else {
      return mid;
    }
  }
  return -1;
}


// used by partition (which is used by qsort_arr)
//
static void swap2(
  char *a[],
  char *b[],
  int i,
  int j
) {
  if (i==j) return;
  char*v;
  v=a[i]; a[i]=a[j]; a[j]=v;
  v=b[i]; b[i]=b[j]; b[j]=v;
}


// used by qsort_arr
//
static int partition(
  char *a[],
  char *b[],
  int left,
  int right,
  int p
) {
  const char *pivotValue = a[p];
  int i;
  swap2(a,b,p,right); // Move pivot to end
  p = left;
  for (i=left; i<right; i++) {
    if (strcmp(a[i],pivotValue)<=0) {
      swap2(a,b,p,i);
      p++;
    }
  }
  swap2(a,b,right,p); // Move pivot to its final place
  return p;
}


//
//
static void qsort_arr(
  char *a[],
  char *b[],
  int left,
  int right
) {
  while (right > left) {
    int p = left + (right-left)/2; //select a pivot
    p = partition(a,b, left, right, p);
    if ((p-1) - left < right - (p+1)) {
      qsort_arr(a,b, left, p-1);
      left  = p+1;
    } else {
      qsort_arr(a,b, p+1, right);
      right = p-1;
    }
  }
}


// Removes extra '0' entries from the string
//
static char* compact(
  char *expr
) {
  int l=strlen(expr);
  int i,j;
  for (i=0,j=0; i<l; i++) {
    if (expr[i]!='0') expr[j++] = expr[i];
  }
  expr[j]=0;
  return expr;
}


// convert 'n1im' to 0n1i0m0 expressed as a string
//
static void expand(
  char *expr,
  const char *pat,
  int l
) {
  int  el = 0;
  char last = '.';
  int  i;
  for (i=0; i<l; i++) {
    char c = pat[i];
    if ( (last<'0' || last>'9')
      && (c   <'0' || c   >'9')
      ) {
      expr[el++] = '0';
    }
    expr[el++] = c;
    last = c;
  }
  if (last<'0' || last>'9') expr[el++] = '0';
  expr[el]=0;
}


// Combine two patterns, i.e. .ad4der + a2d becomes .a2d4der
// The second pattern needs to be a right side match of the first
// (modulo digits)
static char *combine(
  char *expr,
  const char *subexpr
) {
  int l1 = strlen(expr);
  int l2 = strlen(subexpr);
  int off = l1-l2;
  int j;
  // this works also for utf8 sequences because the substring is identical
  // to the last substring-length bytes of expr except for the (single byte)
  // hyphenation encoders
  for (j=0; j<l2; j++) {
    if (subexpr[j]>expr[off+j]) {
      expr[off+j] = subexpr[j];
    }
  }
  return expr;
}

static char *pattab_key[MAXPATHS];
static char *pattab_val[MAXPATHS];
static char *newpattab_key[MAXPATHS];
static char *newpattab_val[MAXPATHS];

int main(int argc, const char* argv[]) {
  FILE *in, *out;
  int   patterns = 0;
  int   newpatterns = 0;
  char format[132]; // 64+65+newline+zero+spare
  int p;
  if (argc!=3) die("Usage: <orig-file> <new-file>\n");
  if ((in = fopen(argv[1],"r"))==NULL) die("Could not read input");
  if ((out = fopen(argv[2],"w"))==NULL) die("Could not create output");
  // read all patterns and split in pure text (_key) & expanded patterns (_val)
  while(fgets(format,132,in) != NULL) {
    int l = strlen(format);
    if (format[l-1]=='\n') { l--; format[l]=0; } // Chomp
    if (format[0]=='%' || format[0]==0) {
      // skip
    } else {
      if (format[l-1]=='%') {
        l--;
        format[l] = 0; // remove '%'
      }
      int i,j;
      char *pat = (char*) malloc(l+1);
      char *org = (char*) malloc(l*2+1);
      if (pat==NULL || org==NULL) die("not enough memory");
      expand(org,format,l);
      // remove hyphenation encoders (digits) from pat
      for (i=0,j=0; i<l; i++) {
        // odd, but utf-8 proof
        char c = format[i];
        if (c<'0' || c>'9') pat[j++]=c;
      }
      pat[j]=0;
      p = patterns;
      pattab_key[patterns]   = pat;
      pattab_val[patterns++] = org;
      if (patterns>MAXPATHS) die("to many base patterns");
    }
  }
  fclose(in);
  // As we use binairy search, make sure it is sorted
  qsort_arr(pattab_key,pattab_val,0,patterns-1);

  for (p=0; p<patterns; p++) {
    char *pat = pattab_key[p];
    int   patsize = strlen(pat);
    int   j,l;
    for (l=1; l<=patsize; l++) {
      for (j=1; j<=l; j++) {
        int i = l-j;
        int  subpat_ndx;
        char subpat[132];
        strncpy(subpat,pat+i,j); subpat[j]=0;
        if ((subpat_ndx = find_in(pattab_key,patterns,subpat))>=0) {
          int   newpat_ndx;
          char *newpat=malloc(l+1);
          if (newpat==NULL) die("not enough memory");
      //printf("%s is embedded in %s\n",pattab_val[subpat_ndx],pattab_val[p]);
          strncpy(newpat, pat+0,l); newpat[l]=0;
          if ((newpat_ndx = find_in(newpattab_key,newpatterns,newpat))<0) {
            char *neworg = malloc(132); // TODO: compute exact length
            if (neworg==NULL) die("not enough memory");
            expand(neworg,newpat,l);
            newpattab_key[newpatterns]   = newpat;
            newpattab_val[newpatterns++] = combine(neworg,pattab_val[subpat_ndx]);
            if (newpatterns>MAXPATHS) die("to many new patterns");
    //printf("%*.*s|%*.*s[%s] (%s|%s) = %s\n",i,i,pat,j,j,pat+i,pat+i+j,pattab_val[p],pattab_val[subpat_ndx],neworg);
          } else {
            free(newpat);
            newpattab_val[newpat_ndx] = combine(
              newpattab_val[newpat_ndx], pattab_val[subpat_ndx] ); 
          }
        }
      }
    }
  }

  /* for some tiny extra speed, one could forget the free()s
   * as the memory is freed anyway on exit().
   * However, the gain is minimal and now the code can be cleanly
   * incorporated into other code */
  for (p=0; p<newpatterns; p++) {
    fprintf(out,"%s\n",compact(newpattab_val[p]));
    free(newpattab_key[p]);
    free(newpattab_val[p]);
  }
  fclose(out);

  for (p=0; p<patterns; p++) {
    free(pattab_key[p]);
    free(pattab_val[p]);
  }
  return 0;
}

Или там же substring.pl

 

[JAW]

Ответ: MS Office какую версию купить? Или поставить Open Office?

Да, если соберёте под Win, просьба кинуть сюда экзешник, я потерял, а здесь он будет не лишним.
Таки косяк по всему Адобу и Опенофису.

И там в архиве с исходниками PDF лежит, его тоже стоит покурить, там описано что изменено и расширено по сравнению с базовыми патернами.

Да, и заодно example.c соберите, если не сложно, для тестирования.

 

[Skvoznyak]

Ответ: MS Office какую версию купить? Или поставить Open Office?

а есть еще мозилловские версии словарей, они тоже косячные?

https://addons.mozilla.org/en-US/firefox/language-tools/

 

[JAW]

Ответ: MS Office какую версию купить? Или поставить Open Office?

а есть еще мозилловские версии словарей, они тоже косячные?

Да. Фактически все свободные алгоритмы переносов базирующиеся на TeX'м алгоритме работают на hunspell (пожалуй я знаю исключения только для мобильных платформ, AlReader, CoolReader, FbReader, т.к. они добавили поддержку паттернов Лянге раньше крупных разработчиков). У Мозиллы скорее всего та же история. Началось с того, что Батов удивился, что словари Лебедева в OO и купленном им Нуке генерируют результат отличный от того, что выдал исходный алгоритм, при том, что он оценивал словари Лебедева очень высоко.

Стали разбираться. Мне на форуме человек, которого я попросил собрать example для теста написал про этот маленький нюанс в readmy. Оказалось, что все его проигнорировали.

HunSpell расширяет синтаксис словарей, но вместе с тем ради оптимизации поиска требует определённой структуры словаря. Указанная программа и приводит к требуемой структуре.

В результате русский в Нуке и Покетбуке привели в порядок. Но вот на монстров повлиять не смогли.

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

Администрации... Просьба выделить сообщения о переносах в отдельную тему.

 

[Skvoznyak]

Ответ: MS Office какую версию купить? Или поставить Open Office?

Что-то у меня ум за разум малость заходит. Конвертнул я переносы Лебедева

и вот результат на первом же слове

санк~~т-пе~~тер~~бург

и что делать, чтобы слова с дефисом переносил нормально? может, другие какие-то брать паттерны?

 

[George]

Ответ оффтопичен: работать в ИнДизайн с Батовскими переносами.

 

[Skvoznyak]

Ответ: Про переносы Hunspell

Я видел Jaw выкладывал поправленные Игорем Батовым паттерны, но ссылка умерла уже.
насколько я понимаю, дефис считается гласной(?), отсюда и проблема. но как это поменять?

вроде получилось - убрал NEXTLEVEL, и стало более похоже на правду

получается Санкт~~-~Пе~~тер~~бург

переноса перед дефисом вроде не возникает

 

[JAW]

Ответ: Про переносы Hunspell

насколько я понимаю, дефис считается гласной(?), отсюда и проблема. но как это поменять?

Там хуже... В TeX есть такое понятие, как категория символов. Нас интересуют две категории, буквы и небуквы. Небуквы не должны вообще попадать на вход хипхенатора, т.е. слово должно дробиться на два. Патерны Лебедева разработаны исходя из того, что дефис не должен попадать на вход хипхенатора.

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

Ответ оффтопичен: работать в ИнДизайн с Батовскими переносами.

Это решение из совсем другой области. Разница в том, что Батовский переносчик работает только для русского. Патерны Лянге почти универсальны, и в этом их сильная сторона. А без косяков автоматические переносы обойтись не могут по любому.


Не по теме:

Я видел Jaw

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

 

[Skvoznyak]

Ответ: Про переносы Hunspell

Там хуже... В TeX есть такое понятие, как категория символов. Нас интересуют две категории, буквы и небуквы. Небуквы не должны вообще попадать на вход хипхенатора, т.е. слово должно дробиться на два. Патерны Лебедева разработаны исходя из того, что дефис не должен попадать на вход хипхенатора.

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

ну нет, в исключения точно не надо. нужны два набора паттернов - один для переносов вокруг дефиса, другой для остальных частей слова (?) по-крайней мере, в readme.compound так написано.
Я пока что убрал NEXTLEVEL, так что у меня как бы один набор - вроде более-менее все

 

[Игорь Батов]

Ответ: Про переносы Hunspell

Разница в том, что Батовский переносчик работает только для русского. Патерны Лянге почти универсальны, и в этом их сильная сторона. А без косяков автоматические переносы обойтись не могут по любому.

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

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

Но необходимо учитывать следующее: набор паттернов и соответственно качество переносов сильно зависят от словаря, по которому генератор паттернов формирует набор правил. batov's dictionary, который я использую, превосходит все известные мне словари (из получивших наибольшее распространение -- словари В. В. Лопатина и А. И. Лебедева -- в разы). Но даже и в этом случае потенциал алгоритма не будет отражен адекватно. В языке TeX просто нет средств, которые позволили бы описать высказывания BaH. То есть конкретный набор паттернов представляет алгоритм расстановки переносов лишь приближенно.

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

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

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

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

 

[Игорь Батов]

Ответ: Про переносы Hunspell

В дополнение к предыдущему.

Сейчас попалось на глаза (1999 TEX Users Group Annual Meeting):
"One of the possible reasons why PATGEN has not been used more extensively may be high investment to create hyphenated list of words, or better, morphological database of given language."

Это то же самое, что и я говорил: "Причины здесь, на мой взгляд, чисто экономические: деятельность эта чрезвычайно трудо- и времяемка..."