Total-fit-algoritmen

Total-fit-algoritmen är den algoritm för brytning av text som Donald Ervin Knuth utvecklade till sitt typsättningssystem TeX i slutet av 1970-talet.

De flesta ordbehandlingsprogram och dylikt använder än i dag (2004) den enklast tänkbara algoritmen för att avgöra var raderna i ett stycke text ska brytas; varje rad fylls på med så mycket text som får plats (eventuellt med avstavning), varefter en brytning infogas. Total-fit-algoritmen ser i stället på stycket som helhet, och ger poäng (demerits) för oönskade effekter såsom avstavning och onormalt avstånd mellan orden. Varje möjlig brytning undersöks, och målet är förstås att ett stycke ska få så få poäng som möjligt.

Implementationsmässigt representeras alla möjliga brytningar av en riktad graf där varje båges längd ges av poängen för den aktuella brytningen. Att finna den bästa styckebrytningen reduceras därmed till att finna den kortaste vägen i grafen, vilket lätt kan lösas.

Algoritmen beskrivs tämligen utförligt med exempel och matematisk bakgrund i Digital Typography.

Förutom i TeX används algoritmen i programmen Adobe InDesign, Groff, hz-program och fmt (ett Unix-kommando).