home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 1 / 1520 < prev    next >
Encoding:
Internet Message Format  |  1990-12-28  |  12.4 KB
  1. From: gtoal@tharr.UUCP (Graham Toal)
  2. Newsgroups: alt.sources
  3. Subject: Spelling utilities; crossword-helper & typo fixer.
  4. Message-ID: <814@tharr.UUCP>
  5. Date: 29 Jun 90 09:49:17 GMT
  6.  
  7. Archive-Name: dawgutils/update1.shar
  8.  
  9. To people who received the last post and got a bit annoyed at the
  10. lack of a makefile, I apologise.  It was my first net posting.  I'll
  11. know better next time.  Meanwhile here's an emergency fix;
  12. cc dawg.c; mv a.out dawg
  13. cc pdawg.c; mv a.out pdawg
  14. cc pack.c; mv a.out pack
  15. cc ppack.c; mv a.out ppack
  16. cc dwgcheck.c; mv a.out dwgcheck
  17. cc pckcheck.c; mv a.out pckcheck
  18. cc tell.c; mv a.out tell
  19. cc proot.c; mv a.out proot
  20. dawg /usr/dict/words dict
  21. pack dict.dwg dict.pck
  22. dwgcheck this and that wroang wurd and another wurd
  23. pckcheck this and that wroang wurd and another wurd
  24. proot meta
  25. tell stoopid speled wurds
  26.  
  27. Hope that helps a bit.  Now for todays additions:
  28. cc typo.c; mv a.out typo
  29. cc cross.c; mv a.out cross
  30. typo spel
  31. cross p\?zz\?e
  32.  
  33. #!/bin/sh-----cut here-----cut here-----cut here-----cut here-----
  34. # shar:    Shell Archiver
  35. #    Run the following text with /bin/sh to create:
  36. #    README #    cross.c #    typo.c 
  37. cat - << \SHAR_EOF > README
  38. This is probably rather early for a follow up to my posting on
  39. spelling checker utilities, but a couple of people have asked for
  40. these...
  41.  
  42. (These programs need dawgutils/* as posted a couple of days ago)
  43.  
  44. typo.c
  45.    A sample program showing how to use the dawg structure to efficiently
  46. correct typos.
  47.  
  48. cross.c
  49.    A 'crossword puzzle' solver - effectively the same as grepping the
  50. word list allowing '?' as a single wild char, eg   cross p?zz?e
  51. would return 'puzzle'.
  52.  
  53. I've also had some interest in my throwaway comments on a replacement
  54. for Soundex; enough to convince me to document it properly and post it
  55. here (a week away at the earliest).  Meanwhile, may I ask again:
  56. If anyone has a dictionary of words and their phonetic representations
  57. could they get in touch please?  Many thanks if you can.
  58.  
  59. Share & Enjoy,
  60.  
  61. Graham Toal (grA@m tOl) <gtoal%uk.ac.ed@nsfnet-relay.ac.uk>
  62. SHAR_EOF
  63. cat - << \SHAR_EOF > cross.c
  64. /* On brain-dead PC's, with MICROSOFT, link with /ST:30000 */
  65. /*
  66.  
  67.     File:          cross.c
  68.     Author:        Graham Toal
  69.     Purpose:       match words with single-char wildcards (cr?ssw?rd p?zzl?s)
  70.     Creation date: 28/06/90 14:01:34
  71.     Lastedit:      28/06/90 14:05:45
  72.  
  73.     Description:
  74.  
  75.     (The nice thing about the dawg structure is that it makes utilities
  76.      like this easy to write; none of these small programs has taken
  77.      more than about an hour. This one took five minutes ;-))
  78.  
  79. */
  80.  
  81.  
  82. /* Manadatory header files */
  83. #include <stdio.h>
  84. #include "dawg.h"
  85. #include "grope.h"
  86. #include "utils.c"
  87.  
  88. /* Headers here as needed on per-program basis */
  89.  
  90. /* Spelling library utilities */
  91. #include "init.c"      /* Loading dicts */
  92.  
  93. #ifdef SYS_MAC
  94. /* To compile with THINK C 4.0, place all the relevant .h and .c
  95.    files in a folder.  Then create a project which contains this main.c
  96.    and the libraries unix and ANSI.
  97. */
  98. #include <unix.h>
  99. #include <stdlib.h>
  100. #include <console.h>
  101. #endif
  102.  
  103. /* This one just gets wrong letters */
  104. int
  105. #ifdef PROTOTYPES
  106. fix_cross(
  107.   NODE PCCRAP *dawg, INDEX i,
  108.   char *word, char *res,
  109.   int len, int *found)
  110. #else
  111. fix_cross(dawg, i, word, res, len, found)
  112. NODE PCCRAP *dawg;
  113. INDEX i;
  114. char *word;
  115. char *res;
  116. int len;
  117. int *found;
  118. #endif
  119. {
  120. int endsword, last, ch, target;
  121. NODE node;
  122. INDEX link;
  123.  
  124.   for (;;) {
  125.     node = dawg[i++];
  126.     ch = (int)((node >> V_LETTER) & M_LETTER);
  127.     last = ((node & (INDEX)M_END_OF_NODE) != 0);
  128.     endsword = ((node & M_END_OF_WORD) != 0);
  129.     link = node & M_NODE_POINTER;
  130.  
  131.     res[len] = ch; res[len+1] = '\0';
  132.     target = ((int)*word)&255;
  133.     if (ch != 0) {
  134.     if (ch == target || target == '?') {
  135.       if (endsword && *(word+1) == '\0') {
  136.         fprintf(stdout, "word: %s\n", res); (*found)++;
  137.       }
  138.       if (*(word+1) != '\0' && link != 0)
  139.         (void) fix_cross(dawg, link, word+1, res, len+1, found);
  140.     }
  141.     }
  142.     if (last) break;
  143.   }
  144.   return(0==0);
  145. }
  146.  
  147. int
  148. #ifdef PROTOTYPES
  149. crossword(NODE PCCRAP *dawg, char *word)
  150. #else
  151. crossword(dawg, word)
  152. NODE PCCRAP *dawg;
  153. char *word;
  154. #endif
  155. {
  156. char result[MAX_WORD_LEN];
  157. int i = 0;
  158.   (void)fix_cross(dawg, (INDEX)ROOT_NODE, word, result, 0, &i);
  159.   return(i);
  160. }
  161.  
  162. int
  163. #ifdef PROTOTYPES
  164. main(int argc, char **argv)
  165. #else
  166. main(argc, argv)
  167. int argc;
  168. char **argv;
  169. #endif
  170. {
  171. NODE PCCRAP *dawg;
  172. INDEX edges;
  173. int each;
  174.  
  175. #ifdef SYS_MAC
  176.   argc = ccommand(&argv);
  177. #endif
  178.  
  179.   /* Your program goes here... */
  180.   if (argc == 1) {
  181.     fprintf(stderr, "usage: %s mispeled wurdz\n", argv[0]);
  182.     exit(EXIT_ERROR);
  183.   }
  184.   if (!dawg_init("", &dawg, &edges)) exit(EXIT_ERROR);
  185.   for (each = 1; each < argc; each++) {
  186.     fprintf(stderr, "* Matches:\n");
  187.     if (!crossword(dawg, argv[each])) {
  188.       fprintf(stderr, "(none found)\n");
  189.     }
  190.     if (each+1 != argc) fprintf(stderr, "\n");
  191.   }
  192.  
  193.   exit(EXIT_OK);
  194. }
  195. SHAR_EOF
  196. cat - << \SHAR_EOF > typo.c
  197. /* On brain-dead PC's, with MICROSOFT, link with /ST:30000 */
  198. /*
  199.  
  200.     File:          typo.c
  201.     Author:        Graham Toal
  202.     Purpose:       offer correct spelling
  203.     Creation date: 27/06/90
  204.     Lastedit:      28/06/90 13:27:03
  205.  
  206.     Description:
  207.  
  208.        Like the unix 'spelltell' command but only fixes typos
  209.     rather than soundslike errors.
  210.  
  211.     See my 'tell' program if you want soundex, or wait a few weeks
  212.     for my new proper phonetic algorithm.
  213.  
  214.     It is a design decision that some of the functions will return the word
  215.     presented if it is in fact correct.  You can call this a bug if you
  216.     prefer.
  217.  
  218.     (The nice thing about the dawg structure is that it makes utilities
  219.      like this easy to write; none of these small programs has taken
  220.      more than about an hour.)
  221.  
  222. */
  223.  
  224.  
  225. /* Manadatory header files */
  226. #include <stdio.h>
  227. #include "dawg.h"
  228. #include "grope.h"
  229. #include "utils.c"
  230.  
  231. /* Headers here as needed on per-program basis */
  232.  
  233. /* Spelling library utilities */
  234. #include "init.c"      /* Loading dicts */
  235. #include "check.c"     /* Simple word-check */
  236.  
  237. #ifdef SYS_MAC
  238. /* To compile with THINK C 4.0, place all the relevant .h and .c
  239.    files in a folder.  Then create a project which contains this main.c
  240.    and the libraries unix and ANSI.
  241. */
  242. #include <unix.h>
  243. #include <stdlib.h>
  244. #include <console.h>
  245. #endif
  246.  
  247. /* This one just gets wrong letters */
  248. int
  249. #ifdef PROTOTYPES
  250. fix_typos(
  251.   NODE PCCRAP *dawg, INDEX i,
  252.   char *word, char *res,
  253.   int len, int errs_allowed, int *found)
  254. #else
  255. fix_typos(dawg, i, word, res, len, errs_allowed, found)
  256. NODE PCCRAP *dawg;
  257. INDEX i;
  258. char *word;
  259. char *res;
  260. int len;
  261. int errs_allowed;
  262. int *found;
  263. #endif
  264. {
  265. int endsword, last, ch;
  266. NODE node;
  267. INDEX link;
  268.  
  269.   for (;;) {
  270.     node = dawg[i++];
  271.     ch = (int)((node >> V_LETTER) & M_LETTER);
  272.     last = ((node & (INDEX)M_END_OF_NODE) != 0);
  273.     endsword = ((node & M_END_OF_WORD) != 0);
  274.     link = node & M_NODE_POINTER;
  275.  
  276.     res[len] = ch; res[len+1] = '\0';
  277.  
  278.     if (ch != 0) {
  279.     if (ch == ((int)*word)&255) {
  280.       if (endsword && *(word+1) == '\0') {
  281.         fprintf(stdout, "word: %s\n", res); (*found)++;
  282.       }
  283.       if (*(word+1) != '\0' && link != 0)
  284.         (void) fix_typos(dawg, link, word+1, res, len+1, errs_allowed, found);
  285.     } else {
  286.       /* Try a different letter here instead? */
  287.       if (errs_allowed > 0) {
  288.         if (endsword && *(word+1) == '\0') {
  289.           fprintf(stdout, "word: %s\n", res); (*found)++;
  290.         }
  291.         if (*(word+1) != '\0' && link != 0)
  292.           (void) fix_typos(
  293.             dawg, link, word+1, res, len+1, errs_allowed-1, found);
  294.       }
  295.     }
  296.     }
  297.     if (last) break;
  298.   }
  299.   return(0==0);
  300. }
  301.  
  302.  
  303. /* And this one corrects omitted letters by inserting one. */
  304.  
  305. int
  306. #ifdef PROTOTYPES
  307. fix_insert(
  308.   NODE PCCRAP *dawg, INDEX i,
  309.   char *word, char *res,
  310.   int len, int errs_allowed, int *found)
  311. #else
  312. fix_insert(dawg, i, word, res, len, errs_allowed, found)
  313. NODE PCCRAP *dawg;
  314. INDEX i;
  315. char *word;
  316. char *res;
  317. int len;
  318. int errs_allowed;
  319. int *found;
  320. #endif
  321. {
  322. int endsword, last, ch;
  323. NODE node;
  324. INDEX link;
  325.  
  326.   for (;;) {
  327.     node = dawg[i++];
  328.     ch = (int)((node >> V_LETTER) & M_LETTER);
  329.     endsword = ((node & M_END_OF_WORD) != 0);
  330.     last = ((node & M_END_OF_NODE) != 0);
  331.  
  332.     link = node & M_NODE_POINTER;
  333.  
  334.     res[len] = ch; res[len+1] = '\0';
  335.  
  336.     if (ch != 0) {
  337.  
  338.     if (endsword && *word == '\0' && errs_allowed > 0) {
  339.       fprintf(stdout, "word: %s\n", res); (*found)++;
  340.     }
  341.  
  342.     if (ch == ((int)*word)&255) {
  343.       if (endsword && *(word+1) == '\0') {
  344.         fprintf(stdout, "word: %s\n", res); (*found)++;
  345.         /*return(0==0);*/
  346.       }
  347.       if (*word == '\0') {
  348.         if (errs_allowed > 0)
  349.           (void) fix_insert(
  350.             dawg, link, word+1, res, len+1, errs_allowed, found);
  351.       } else {
  352.         if (link != 0)
  353.           (void) fix_insert(
  354.             dawg, link, word+1, res, len+1, errs_allowed, found);
  355.       }
  356.     }
  357.     /* Insert this letter (len+1) and see if rest matches */
  358.     if (errs_allowed > 0) {
  359.       if (link != 0)
  360.         (void) fix_insert(dawg, link, word, res, len+1, errs_allowed-1, found);
  361.     }
  362.     }
  363.     if (last) break;
  364.   }
  365.   return(0==0);
  366. }
  367.  
  368.  
  369. /* And finally catch inserted letters by deleting one */
  370.  
  371. int
  372. #ifdef PROTOTYPES
  373. fix_delete(
  374.   NODE PCCRAP *dawg, INDEX i,
  375.   char *word, char *res,
  376.   int len, int errs_allowed, int *found)
  377. #else
  378. fix_delete(dawg, i, word, res, len, errs_allowed, found)
  379. NODE PCCRAP *dawg;
  380. INDEX i;
  381. char *word;
  382. char *res;
  383. int len;
  384. int errs_allowed;
  385. int *found;
  386. #endif
  387. {
  388. int endsword, last, ch;
  389. NODE node;
  390. INDEX link;
  391.  
  392.   if (errs_allowed > 0) {
  393.     if (*(word+1) != '\0') {
  394.       (void) fix_delete(dawg, i, word+1, res, len, errs_allowed-1, found);
  395.     } else {
  396.       /* Shouldn't get this far, but does :-( */
  397.       return(0==0);
  398.     }
  399.   }
  400.   for (;;) {
  401.     node = dawg[i++];
  402.     ch = (int)((node >> V_LETTER) & M_LETTER);
  403.     endsword = ((node & M_END_OF_WORD) != 0);
  404.     last = ((node & M_END_OF_NODE) != 0);
  405.  
  406.     link = node & M_NODE_POINTER;
  407.  
  408.     res[len] = ch; res[len+1] = '\0';
  409.  
  410.     if (ch != 0) {
  411.     if (ch == ((int)*word)&255) {
  412.  
  413.       if (errs_allowed > 0 &&
  414.           endsword &&
  415.           *(word+1) != '\0' &&
  416.           *(word+2) == '\0') {
  417.         fprintf(stdout, "word: %s\n", res); (*found)++;
  418.       }
  419.  
  420.       if (endsword && *(word+1) == '\0') {
  421.         fprintf(stdout, "word: %s\n", res); (*found)++;
  422.         return(0==0);
  423.       }
  424.       if (*(word+1) != '\0' && link != 0)
  425.         (void) fix_delete(dawg, link, word+1, res, len+1, errs_allowed, found);
  426.     }
  427.     }
  428.  
  429.     if (last) break;
  430.   }
  431.   return(0==0);
  432. }
  433.  
  434.  
  435. int
  436. #ifdef PROTOTYPES
  437. dawg_typo(NODE PCCRAP *dawg, char *word)
  438. #else
  439. dawg_typo(dawg, word)
  440. NODE PCCRAP *dawg;
  441. char *word;
  442. #endif
  443. {
  444. char result[MAX_WORD_LEN];
  445. int i = 0;
  446.   (void)fix_typos(dawg, (INDEX)ROOT_NODE, word, result, 0, 1, &i);
  447.   return(i);
  448. }
  449.  
  450. int
  451. #ifdef PROTOTYPES
  452. dawg_insert(NODE PCCRAP *dawg, char *word)
  453. #else
  454. dawg_insert(dawg, word)
  455. NODE PCCRAP *dawg;
  456. char *word;
  457. #endif
  458. {
  459. char result[MAX_WORD_LEN];
  460. int i = 0;
  461.   (void)fix_insert(dawg, (INDEX)ROOT_NODE, word, result, 0, 1, &i);
  462.   return(i);
  463. }
  464.  
  465. int
  466. #ifdef PROTOTYPES
  467. dawg_delete(NODE PCCRAP *dawg, char *word)
  468. #else
  469. dawg_delete(dawg, word)
  470. NODE PCCRAP *dawg;
  471. char *word;
  472. #endif
  473. {
  474. char result[MAX_WORD_LEN];
  475. int i = 0;
  476.   (void)fix_delete(dawg, (INDEX)ROOT_NODE, word, result, 0, 1, &i);
  477.   return(i);
  478. }
  479.  
  480. int
  481. #ifdef PROTOTYPES
  482. dawg_transpose(NODE PCCRAP *dawg, char *word)
  483. #else
  484. dawg_transpose(dawg, word)
  485. NODE PCCRAP *dawg;
  486. char *word;
  487. #endif
  488. {
  489. int i = 0, l, c;
  490.   for (l = 0; word[l+1] != '\0'; l++) {
  491.     c = word[l]; word[l] = word[l+1]; word[l+1] = c;
  492.     if (dawg_check(dawg, word)) {
  493.       i++;
  494.       fprintf(stdout, "word: %s\n", word);
  495.     }
  496.     c = word[l]; word[l] = word[l+1]; word[l+1] = c;
  497.   }
  498.   return(i /* != 0 */);
  499. }
  500.  
  501.  
  502. int
  503. #ifdef PROTOTYPES
  504. main(int argc, char **argv)
  505. #else
  506. main(argc, argv)
  507. int argc;
  508. char **argv;
  509. #endif
  510. {
  511. NODE PCCRAP *dawg;
  512. INDEX edges;
  513. int each;
  514.  
  515. #ifdef SYS_MAC
  516.   argc = ccommand(&argv);
  517. #endif
  518.  
  519.   /* Your program goes here... */
  520.   if (argc == 1) {
  521.     fprintf(stderr, "usage: %s mispeled wurdz\n", argv[0]);
  522.     exit(EXIT_ERROR);
  523.   }
  524.   if (!dawg_init("", &dawg, &edges)) exit(EXIT_ERROR);
  525.   for (each = 1; each < argc; each++) {
  526.     fprintf(stderr, "* Wrong char:\n");
  527.     if (!dawg_typo(dawg, argv[each])) {
  528.       fprintf(stderr, "(none found)\n");
  529.     }
  530.     fprintf(stderr, "* Omitted char\n");
  531.     if (!dawg_insert(dawg, argv[each])) {
  532.       fprintf(stderr, "(none found)\n");
  533.     }
  534.     fprintf(stderr, "* Inserted char:\n");
  535.     if (!dawg_delete(dawg, argv[each])) {
  536.       fprintf(stderr, "(none found)\n");
  537.     }
  538.     fprintf(stderr, "* Transposed char:\n");
  539.     if (!dawg_transpose(dawg, argv[each])) {
  540.       fprintf(stderr, "(none found)\n");
  541.     }
  542.     if (each+1 != argc) fprintf(stderr, "\n");
  543.   }
  544.  
  545.   exit(EXIT_OK);
  546. }
  547. SHAR_EOF
  548.