+ /* Computing the optimal way to parse strings to insert abbreviations with dynamic programming */
+ /* (ref: R.A. Wagner , "Common phrases and minimum-space text storage", Commun. ACM, 16 (3) (1973)) */
+ /* We compute this optimal way here; it's stored in abbreviations_optimal_parse_schedule */
+ if (economy_switch)
+ {
+ uchar *q, c;
+ int l, min_score, from;
+ int text_in_length;
+
+ text_in_length = strlen( (char*) text_in);
+ ensure_memory_list_available(&abbreviations_optimal_parse_schedule_memlist, text_in_length);
+ ensure_memory_list_available(&abbreviations_optimal_parse_scores_memlist, text_in_length+1);
+
+ abbreviations_optimal_parse_scores[text_in_length] = 0;
+ for(j=text_in_length-1; j>=0; j--)
+ { /* Initial values: empty schedule, score = just write the letter without abbreviating. */
+ abbreviations_optimal_parse_schedule[j] = -1;
+ min_score = zchar_weight(text_in[j]) + abbreviations_optimal_parse_scores[j+1];
+ /* If there's an abbreviation starting with that letter... */
+ if ( (from = abbrevs_lookup[text_in[j]]) != -1)
+ {
+ c = text_in[j];
+ /* Loop on all abbreviations starting with what is in c. */
+ for (k=from, q=(uchar *)abbreviations_at+from*MAX_ABBREV_LENGTH;
+ (k<no_abbreviations)&&(c==q[0]); k++, q+=MAX_ABBREV_LENGTH)
+ {
+ /* Let's compare; we also keep track of the length of the abbreviation. */
+ for (l=1; q[l]!=0; l++)
+ { if (text_in[j+l]!=q[l]) {goto NotMatched;}
+ }
+ /* We have a match (length l), but is it smaller in size? */
+ if (min_score > 2 + abbreviations_optimal_parse_scores[j+l])
+ { /* It is indeed smaller, so let's write it down in our schedule. */
+ min_score = 2 + abbreviations_optimal_parse_scores[j+l];
+ abbreviations_optimal_parse_schedule[j] = k;
+ }
+ NotMatched: ;
+ }
+ }
+ /* We gave it our best, this is the smallest we got. */
+ abbreviations_optimal_parse_scores[j] = min_score;
+ }
+ }
+
+
+