home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1994 March / Source_Code_CD-ROM_Walnut_Creek_March_1994.iso / compsrcs / misc / volume37 / phon2alf / part01 < prev    next >
Encoding:
Text File  |  1993-05-15  |  24.7 KB  |  847 lines

  1. Newsgroups: comp.sources.misc
  2. From: dave@devteq.co.uk (Dave Thomas)
  3. Subject: v37i055:  phone2alf - guess sensible words from a phone number, Part01/01
  4. Message-ID: <1993May16.005347.15283@sparky.imd.sterling.com>
  5. X-Md4-Signature: 02b36b8a396558f7562d560dde569c82
  6. Date: Sun, 16 May 1993 00:53:47 GMT
  7. Approved: kent@sparky.imd.sterling.com
  8.  
  9. Submitted-by: dave@devteq.co.uk (Dave Thomas)
  10. Posting-number: Volume 37, Issue 55
  11. Archive-name: phone2alf/part01
  12. Environment: C
  13.  
  14. This is a set of three programs which together make slightly
  15. better than random guesses at words that can be made up from
  16. phone numbers (actually any numbers).
  17.  
  18. We apply a simple heuristic to try to put likely English
  19. (actually any language) words at the top of the list of
  20. permutations. Often these words aren't English, but the
  21. should have been. :-)
  22.  
  23. This was all written as a bit of fun, and is released without
  24. restriction for non-commercial use. I'd be interested in any
  25. feedback. 
  26.  
  27.  From_____________________________________________________________________
  28.  | Dave Thomas - Devteq Ltd - 18 Thames St - Windsor - Berks SL4 1PL - UK |
  29.  | Tel: +44 753 830333  - Fax: +44 753 831645  - email: dave@devteq.co.uk |
  30.   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
  31. -----------------------v--- cut here ---v--------------------------------
  32. #! /bin/sh
  33. # This is a shell archive.  Remove anything before this line, then feed it
  34. # into a shell via "sh file" or similar.  To overwrite existing files,
  35. # type "sh file -c".
  36. # Contents:  README Makefile generate num2alpha.c score.c threes.c
  37. # Wrapped by kent@sparky on Sat May 15 19:47:51 1993
  38. PATH=/bin:/usr/bin:/usr/ucb:/usr/local/bin:/usr/lbin ; export PATH
  39. echo If this archive is complete, you will see the following message:
  40. echo '          "shar: End of archive 1 (of 1)."'
  41. if test -f 'README' -a "${1}" != "-c" ; then 
  42.   echo shar: Will not clobber existing file \"'README'\"
  43. else
  44.   echo shar: Extracting \"'README'\" \(2799 characters\)
  45.   sed "s/^X//" >'README' <<'END_OF_FILE'
  46. XPHONE2ALF    - generate sensible words from a phone number
  47. X
  48. XThis is a set of three programs which together make slightly
  49. Xbetter than random guesses at words that can be made up from
  50. Xphone numbers (actually any numbers).
  51. X
  52. XClearly, generating the possible permutations of 'words' from
  53. Xa phone number is simple. However with over 2000 possible
  54. Xpermutations of a 7 digit number, looking for the word that's
  55. Xjust right can take a while.
  56. X
  57. XTo speed things up, we apply a simple heuristic, based on a
  58. Xspelling checking algorithm I remember vaguely from a mid
  59. X70's CACM or SigPLAN. Before starting, we build up a
  60. Xfrequency table for each of the 21952 possible combinations
  61. Xof three consecutive letters (including start and end of word
  62. Xas letters) in a (largish) sample of text representative of
  63. Xthe language we want to test against. Thus for the word
  64. X'Thus' we would count
  65. X
  66. X    <SOW>th
  67. X    thu
  68. X    hus
  69. X    us<EOW>
  70. X
  71. XTo reduce the size of the table, and prevent possible
  72. Xoverflow issues, we actually store ~log2(frequency). 
  73. X
  74. XWe then look at the words generated by our phone number. For
  75. Xeach, we add together the previously observed trigraph
  76. Xfrequencies for the letters in that word. This gives us a
  77. Xscore. By sorting the words by that score, we put the words
  78. Xmost likely to be in our target language set first. 
  79. X
  80. XTo use this package, first determine a set of files and/or
  81. Xdirectories contains words you feel respresentative of your
  82. Xtarget. The bigger, the better. As distributed, the program
  83. Xwill look through some of your usenet directories. Edit the
  84. XMakefile to point to these.
  85. X
  86. XRun 'make'. This generates three programs.
  87. X
  88. X    'threes'   does the counting of frequencies. The makefile
  89. X               will invoke this automatically to generate the
  90. X           file 'freq.table'.
  91. X           
  92. X 'num2alpha'   takes a number as a parameter and generates on
  93. X            stdout all words that can be made using the
  94. X           letters on a phone pad corresponding to the digits
  95. X           in the number.
  96. X           
  97. X     'score'   Takes a list of words and scores them according
  98. X               to the previously observed frequencies of
  99. X               occurance of each words constituent trigraphs.
  100. X           
  101. X           
  102. XTo generate a sorted list of words for a phone number, run the
  103. Xshell script 
  104. X
  105. X           generate  <number>
  106. X         
  107. X.....
  108. X
  109. XThis was all written as a bit of fun, and is released without
  110. Xrestriction for non-commercial use. I'd be interested in any
  111. Xfeedback. If anyone wants to make a million out of this, I'll
  112. Xtake my cut :-)
  113. X
  114. X
  115. XFrom_____________________________________________________________________
  116. X| Dave Thomas - Devteq Ltd - 18 Thames St - Windsor - Berks SL4 1PL - UK |
  117. X| Tel: +44 753 830333  - Fax: +44 753 831645  - email: dave@devteq.co.uk |
  118. X ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
  119. X
  120. X
  121. X
  122. END_OF_FILE
  123.   if test 2799 -ne `wc -c <'README'`; then
  124.     echo shar: \"'README'\" unpacked with wrong size!
  125.   fi
  126.   # end of 'README'
  127. fi
  128. if test -f 'Makefile' -a "${1}" != "-c" ; then 
  129.   echo shar: Will not clobber existing file \"'Makefile'\"
  130. else
  131.   echo shar: Extracting \"'Makefile'\" \(1721 characters\)
  132.   sed "s/^X//" >'Makefile' <<'END_OF_FILE'
  133. X#
  134. X#    Generate the various programs and datafiles needed to
  135. X#    play with the 'English from phone numbers' suite. See
  136. X#    README for more info.
  137. X#
  138. X#
  139. X#    dave@devteq.co.uk
  140. X#
  141. X
  142. X#
  143. X#    WORDS points at a set of files and/or directories containing
  144. X#       text in the language you want to use. Be careful not to include
  145. X#    too many non text files, as these will degrade the result.
  146. X#    In particular, if you're using the USENET feed as a source,
  147. X#    avoid .binaries & .sources (becuase uuencoded stuff contains
  148. X#    patterns you don't want to accept and programmer can't spell
  149. X#    in the first place!)
  150. X#
  151. X
  152. XWORDS    =    /usr/spool/news/comp/lang /usr/spool/news/alt/politics
  153. X
  154. XCFLAGS    =    -O
  155. X
  156. X#######################################################################
  157. X#
  158. X#    Rest shouldn't need changing
  159. X#
  160. X
  161. XSHAR_FILES = Makefile README generate num2alpha.c score.c threes.c
  162. X
  163. Xall:        threes num2alpha score freq.table
  164. X
  165. X#
  166. X#    The THREEs program generates the original frequency tables
  167. X#    based on a set of input files & directories
  168. X
  169. Xthrees:        threes.o
  170. X        cc -o threes threes.o
  171. X
  172. X#
  173. X#    Num2Alpha generates all possible letter combinations corresponding
  174. X#    to a given phone number
  175. X
  176. Xnum2alpha:    num2alpha.o
  177. X        cc -o num2alpha num2alpha.o
  178. X
  179. X#
  180. X#    Score takes a set of words (normally generated by num2alpha) and
  181. X#    generates a score based on the frequencies of each word's letters
  182. X#    in the original sample set (generated by threes)
  183. X        
  184. Xscore:        score.o
  185. X        cc -o score score.o
  186. X
  187. X
  188. X#
  189. X#    Generate the binary frequency table based on the given set
  190. X#    of files & directories. This will always be into a file called
  191. X#    freq.table
  192. X    
  193. Xfreq.table:    threes
  194. X        threes $(WORDS)
  195. X
  196. X
  197. X#
  198. X#    Save 'em all away
  199. X#
  200. X
  201. Xshar:        phone2alf.shar
  202. X                 
  203. Xphone2alf.shar:    $(SHAR_FILES)
  204. X        shar -d -v $(SHAR_FILES) >phone2alf.shar
  205. X        
  206. END_OF_FILE
  207.   if test 1721 -ne `wc -c <'Makefile'`; then
  208.     echo shar: \"'Makefile'\" unpacked with wrong size!
  209.   fi
  210.   # end of 'Makefile'
  211. fi
  212. if test -f 'generate' -a "${1}" != "-c" ; then 
  213.   echo shar: Will not clobber existing file \"'generate'\"
  214. else
  215.   echo shar: Extracting \"'generate'\" \(642 characters\)
  216.   sed "s/^X//" >'generate' <<'END_OF_FILE'
  217. X#!/bin/sh
  218. X#
  219. X#    Given a phone number as $1, generate a sorted list
  220. X#    words where each letter comes from the characters on
  221. X#    a telephone keypad corresponding to the input number. 
  222. X#    These words are sorted according to their liklihood of
  223. X#    being approximately 'English' (or to be more accurate
  224. X#    their nearness to an arbitrary sample of text previously
  225. X#    loaded into 'freq.table' by the trieme program)
  226. X#
  227. X#    dave@devteq.co.uk
  228. X
  229. Xif [ $# -ne 1 ]; then
  230. X  echo usage: $0 \<phone no\>
  231. X  exit 1
  232. Xfi
  233. X
  234. Xif [ ! -f freq.table ]; then
  235. X   echo You must run \'threes\' first to generate the frequency table
  236. X   exit 2
  237. Xfi
  238. X
  239. Xnum2alpha $1 | score | sort -rn         
  240. X
  241. END_OF_FILE
  242.   if test 642 -ne `wc -c <'generate'`; then
  243.     echo shar: \"'generate'\" unpacked with wrong size!
  244.   fi
  245.   chmod +x 'generate'
  246.   # end of 'generate'
  247. fi
  248. if test -f 'num2alpha.c' -a "${1}" != "-c" ; then 
  249.   echo shar: Will not clobber existing file \"'num2alpha.c'\"
  250. else
  251.   echo shar: Extracting \"'num2alpha.c'\" \(3270 characters\)
  252.   sed "s/^X//" >'num2alpha.c' <<'END_OF_FILE'
  253. X/***********************************************************************\
  254. X* num2alpha.c  *    Convert a phone number to alpha strings.            *                                    *
  255. X\************************************************************************
  256. X*                                               *
  257. X*    Given a phone number, generate all possible alpha strings          *
  258. X*    corresponding to the labels on those digits on a standard phone.   *
  259. X*                                    *
  260. X*_______________________________________________________________________*
  261. X* Dave Thomas - Devteq Ltd - 18 Thames St - Windsor - Berks SL4 1PL - UK*
  262. X* Tel: +44 753 830333  - Fax: +44 753 831645  - email: dave@devteq.co.uk*
  263. X*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  264. X*                                    *
  265. X\***********************************************************************/
  266. X
  267. X#include <stdio.h>
  268. X#include <stdlib.h>
  269. X#include <ctype.h>
  270. X#include <memory.h>
  271. X
  272. X/***
  273. X*    Array indexed by 'digit' - '0', gives set of each alpha
  274. X*    character for that digit
  275. X***/
  276. X
  277. Xchar *alphas[10] =
  278. X{
  279. X  /* 0 */ "0",
  280. X  /* 1 */ "1",
  281. X  /* 2 */ "abc",
  282. X  /* 3 */ "def",
  283. X  /* 4 */ "ghi",
  284. X  /* 5 */ "jkl",
  285. X  /* 6 */ "mno",
  286. X  /* 7 */ "prs",
  287. X  /* 8 */ "tuv",
  288. X  /* 9 */ "wxy",
  289. X};
  290. X
  291. X/***
  292. X*    array holds result of each permutation
  293. X***/
  294. X
  295. Xchar result[20] =
  296. X{0};                /* any bigger & we'll take forever anyway */
  297. X
  298. Xvoid
  299. Xperm (const char *pNumber, int offset)
  300. X{
  301. X  if (pNumber[offset] == 0)
  302. X    {
  303. X      puts (result);
  304. X    }
  305. X  else
  306. X    {
  307. X      char *nextAlpha = alphas[pNumber[offset] - '0'];
  308. X
  309. X      while (*nextAlpha)
  310. X    {
  311. X      result[offset] = *nextAlpha;
  312. X      perm (pNumber, offset + 1);
  313. X      nextAlpha++;
  314. X    }
  315. X    }
  316. X}
  317. X
  318. X
  319. X/***********************************************************************\
  320. X* convert      *  Convert a number to alpha strings                     *                                    *
  321. X\************************************************************************
  322. X*                                               *
  323. X* Convert a single number to its corrsponding alpha strings.            *
  324. X*                                    *
  325. X\***********************************************************************/
  326. X
  327. Xvoid
  328. Xconvert (const char *pNumber)
  329. X{
  330. X  register const char *p;
  331. X
  332. X  /***
  333. X  *    First check its actually a number
  334. X  ***/
  335. X
  336. X  for (p = pNumber; *p; p++)
  337. X    if (!isdigit (*p))
  338. X      {
  339. X    fprintf (stderr, "'%s' is not a number - skipping...\n", pNumber);
  340. X    return;
  341. X      }
  342. X    else if ((*p == '0') || (*p == '1'))
  343. X      {
  344. X    fprintf (stderr, "'%s' contains a '%c' - this doesn't"
  345. X         " have a letter associated with it\n", pNumber, *p);
  346. X    return;
  347. X      }
  348. X
  349. X  if ((p - pNumber) >= sizeof (result))
  350. X    {
  351. X      fprintf (stderr, "Number '%s' is longer than %d characters\n",
  352. X           pNumber, sizeof (result) - 1);
  353. X      return;
  354. X    }
  355. X
  356. X  perm (pNumber, 0);
  357. X}
  358. X
  359. X/***********************************************************************\
  360. X* main         *  Generate alpha strings from number                    *                                    *
  361. X\************************************************************************
  362. X*                                               *
  363. X* Accept a number from the argument list, and generate the cross        *
  364. X* product of its digits and those digits labels on a standard phone.    *
  365. X*                                    *
  366. X\***********************************************************************/
  367. X
  368. Xint
  369. Xmain (int argc, char **argv)
  370. X{
  371. X  argc--;
  372. X  argv++;
  373. X
  374. X  while (argc--)
  375. X    convert (*argv++);
  376. X
  377. X  return 0;
  378. X}
  379. END_OF_FILE
  380.   if test 3270 -ne `wc -c <'num2alpha.c'`; then
  381.     echo shar: \"'num2alpha.c'\" unpacked with wrong size!
  382.   fi
  383.   # end of 'num2alpha.c'
  384. fi
  385. if test -f 'score.c' -a "${1}" != "-c" ; then 
  386.   echo shar: Will not clobber existing file \"'score.c'\"
  387. else
  388.   echo shar: Extracting \"'score.c'\" \(4694 characters\)
  389.   sed "s/^X//" >'score.c' <<'END_OF_FILE'
  390. X
  391. X/***********************************************************************\
  392. X* score.c      *    Calculate trieme score for a set of words           *                                    *
  393. X\************************************************************************
  394. X*                                               *
  395. X*    Someone's previously sampled a whole lot of English words, and     *
  396. X*    generated a table of frequencies for all the triemes (groups of    *
  397. X*    3 consecutive letters) in that sample. We now read in a set of     *
  398. X*    words from stdin and add together the previously accumulated       *
  399. X*    frequencies for each trieme in each word. For each word, when then *
  400. X*    output the total score for that word.                         *
  401. X*                                    *
  402. X*    Why?                                                               *
  403. X*                                    *
  404. X*    Well - the word list is generated from (say) all the permutations  *
  405. X*    of letters corresponding to a phone number. By scoring each        *
  406. X*    against a population of triemes, we can identify those combinations*
  407. X*    of letters that are most likely to be words from that population.  *
  408. X*    We can then more readily find appropriate nmemonics!           *
  409. X*                                    *
  410. X* Released to the net for free use. Clearly the author accepts no     *
  411. X* responsibility for anything to do with this program. Share & enjoy     *
  412. X*                                    *
  413. X*_______________________________________________________________________*
  414. X* Dave Thomas - Devteq Ltd - 18 Thames St - Windsor - Berks SL4 1PL - UK*
  415. X* Tel: +44 753 830333  - Fax: +44 753 831645  - email: dave@devteq.co.uk*
  416. X*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  417. X*                                    *
  418. X\***********************************************************************/
  419. X
  420. X#include <stdio.h>
  421. X#include <stdlib.h>
  422. X
  423. X#define FREQ_TABLE_FILE "freq.table"
  424. X
  425. X#define SOW ('a'-1)        /* start & end of word 'pseudo' characters */
  426. X#define EOW ('z'+1)
  427. X
  428. X#if !defined(TRUE)
  429. X#define TRUE  1
  430. X#define  FALSE 0
  431. X#endif
  432. X
  433. Xunsigned char count[28][28][28] =
  434. X{0};                /* trieme counter */
  435. X
  436. X/***********************************************************************\
  437. X* handleWord   *  Accumulate trieme frequencies for a single word       *                                    *
  438. X\************************************************************************
  439. X*                                               *
  440. X* Given a word delimited by SOW/EOW, calculate the frequencies for      *
  441. X* each trieme (including the delimters)                 *
  442. X*                                    *
  443. X\***********************************************************************/
  444. X
  445. X#define INDEX(ch) (ch-SOW)
  446. X
  447. Xvoid
  448. XhandleWord (char *pWord)
  449. X{
  450. X  register char *p;
  451. X  int score = 0;
  452. X
  453. X  for (p = pWord; *(p + 1) != EOW; p++)
  454. X    {
  455. X      score += count[INDEX (*p)][INDEX (p[1])][INDEX (p[2])];
  456. X    }
  457. X
  458. X  p[1] = 0;            /* remove EOW */
  459. X
  460. X  printf ("%-5d %s\n", score, pWord + 1);
  461. X}
  462. X
  463. X/***********************************************************************\
  464. X* processFile  *  Process an individual file                            *                                    *
  465. X\************************************************************************
  466. X*                                               *
  467. X* Go through a file extracting word by word. For each, calll handleWord *
  468. X* to build trieme frequencies. If we ever come across a NUL in the file *
  469. X* we give it - it must be a binary file.                *
  470. X\***********************************************************************/
  471. X
  472. Xvoid
  473. XprocessFile (FILE * f)
  474. X{
  475. X  char word[50];        /* collects current word */
  476. X  int iWord;            /* index into it */
  477. X
  478. X  int fInWord = FALSE;
  479. X  int ch;
  480. X
  481. X  while (((ch = fgetc (f)) != EOF) && ch)
  482. X    {
  483. X
  484. X      if (!fInWord && isalpha (ch))
  485. X    {
  486. X      fInWord = TRUE;
  487. X      iWord = 0;
  488. X      word[iWord++] = SOW;
  489. X    }
  490. X
  491. X      if (fInWord)
  492. X    {
  493. X      if (!isalpha (ch))
  494. X        {
  495. X          if (iWord > 4)
  496. X        {
  497. X          word[iWord] = EOW;
  498. X          handleWord (word);
  499. X        }
  500. X          fInWord = FALSE;
  501. X        }
  502. X      else
  503. X        {
  504. X          word[iWord] = tolower (ch);
  505. X          if (iWord < (sizeof (word) - 1))
  506. X        iWord++;
  507. X        }
  508. X
  509. X    }
  510. X    }
  511. X
  512. X}
  513. X
  514. X/***********************************************************************\
  515. X* main         *  Parse args and run analysis                           *                                    *
  516. X\************************************************************************
  517. X*                                               *
  518. X* Trundle through the arguments. For each file found, process it.       *
  519. X* For each directory, process it recursively.               *
  520. X*                                    *
  521. X\***********************************************************************/
  522. X
  523. Xint
  524. Xmain ()
  525. X{
  526. X  FILE *f = fopen (FREQ_TABLE_FILE, "r");
  527. X
  528. X  if (f == NULL)
  529. X    {
  530. X      perror (FREQ_TABLE_FILE);
  531. X      return 0;
  532. X    }
  533. X
  534. X  if (fread (count, 1, sizeof (count), f) != sizeof (count))
  535. X    {
  536. X      fprintf (stderr, "Couldn't read in '%s'\n", FREQ_TABLE_FILE);
  537. X      return 0;
  538. X    }
  539. X
  540. X  fclose (f);
  541. X
  542. X
  543. X  processFile (stdin);
  544. X  return 0;
  545. X
  546. X}
  547. END_OF_FILE
  548.   if test 4694 -ne `wc -c <'score.c'`; then
  549.     echo shar: \"'score.c'\" unpacked with wrong size!
  550.   fi
  551.   # end of 'score.c'
  552. fi
  553. if test -f 'threes.c' -a "${1}" != "-c" ; then 
  554.   echo shar: Will not clobber existing file \"'threes.c'\"
  555. else
  556.   echo shar: Extracting \"'threes.c'\" \(7110 characters\)
  557.   sed "s/^X//" >'threes.c' <<'END_OF_FILE'
  558. X/***********************************************************************\
  559. X* threes.c * Calculate trigraph frequencies for a group of files        *
  560. X\************************************************************************
  561. X*                                               *
  562. X*    Given a group of files or directories, calculate the frequencies   *
  563. X*    of each group of three adjacent letters in each word. We treat     *
  564. X*    start of word and end of word as special letters.          *
  565. X*                                    *
  566. X*    The output is an array of 28^3 unsigned chars, corresponding to    *
  567. X*    log(2) of the frequencies (except log(2)(0) == 0).            *
  568. X*                                    *
  569. X*    This is a simple precursor to finding most likely English words    *
  570. X*    amongst perumations of letters generated from (for example)    *
  571. X*    phone numbers.                             *
  572. X*                                    *
  573. X* Released to the net for free use. Clearly the author accepts no     *
  574. X* responsibility for anything to do with this program. Share & enjoy     *
  575. X*                                    *
  576. X*_______________________________________________________________________*
  577. X* Dave Thomas - Devteq Ltd - 18 Thames St - Windsor - Berks SL4 1PL - UK*
  578. X* Tel: +44 753 830333  - Fax: +44 753 831645  - email: dave@devteq.co.uk*
  579. X*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  580. X*                                    *
  581. X\***********************************************************************/
  582. X
  583. X#include <limits.h>
  584. X#include <stdio.h>
  585. X#include <stdlib.h>
  586. X#include <ftw.h>
  587. X#include <ctype.h>
  588. X#include <sys/types.h>
  589. X#include <sys/stat.h>
  590. X
  591. X#define SOW ('a'-1)        /* start & end of word 'pseudo' characters */
  592. X#define EOW ('z'+1)
  593. X
  594. X#if !defined(TRUE)
  595. X#define TRUE  1
  596. X#define  FALSE 0
  597. X#endif
  598. X
  599. Xtypedef unsigned int CountType;
  600. X#define COUNT_MAX UINT_MAX    /* depends on CountType */
  601. X/* MUST BE 2^n -1 */
  602. X
  603. XCountType count[28][28][28] = {0};     /* trigraph counter */
  604. X
  605. X/***********************************************************************\
  606. X* handleWord   *  Accumulate trigraph frequencies for a single word     *
  607. X\************************************************************************
  608. X*                                               *
  609. X* Given a word delimited by SOW/EOW, calculate the frequencies for      *
  610. X* each trigraph(including the delimters)                 *
  611. X*                                    *
  612. X\***********************************************************************/
  613. X
  614. X#define INDEX(ch) (ch-SOW)
  615. X
  616. Xvoid
  617. XhandleWord (char *pWord)
  618. X{
  619. X  register char *p;
  620. X
  621. X
  622. X  for (p = pWord; *(p + 1) != EOW; p++)
  623. X    {
  624. X      if (++count[INDEX (*p)][INDEX (p[1])][INDEX (p[2])] == COUNT_MAX)
  625. X    {
  626. X      printf ("Trieme overflow \"%c%c%c\"\n", p[0], p[1], p[2]);
  627. X      count[INDEX (*p)][INDEX (p[1])][INDEX (p[2])] -= 1000;
  628. X    }
  629. X    }
  630. X
  631. X}
  632. X
  633. X#undef INDEX
  634. X
  635. X
  636. X/***********************************************************************\
  637. X* processFile * Process an individual file                         *
  638. X\************************************************************************
  639. X*                                               *
  640. X* Go through a file extracting word by word. For each, calll handleWord *
  641. X* to build trigraph frequencies. If we ever come across a NUL in the     *
  642. X* file we give it - it must be a binary file, so we stop processing.    *
  643. X\***********************************************************************/
  644. X
  645. Xvoid
  646. XprocessFile (FILE * f)
  647. X{
  648. X  char word[50];        /* collects current word */
  649. X  int iWord;            /* index into it */
  650. X
  651. X  int fInWord = FALSE;
  652. X  int ch;
  653. X
  654. X  while (((ch = fgetc (f)) != EOF) && ch)
  655. X    {
  656. X
  657. X      if (!fInWord && isalpha (ch))
  658. X    {
  659. X      fInWord = TRUE;
  660. X      iWord = 0;
  661. X      word[iWord++] = SOW;
  662. X    }
  663. X
  664. X      if (fInWord)
  665. X    {
  666. X      if (!isalpha (ch))
  667. X        {
  668. X          if (iWord > 4)    /* ignore words < 3 chars */
  669. X        {
  670. X          word[iWord] = EOW;
  671. X          handleWord (word);
  672. X        }
  673. X          fInWord = FALSE;
  674. X        }
  675. X      else
  676. X        {
  677. X          word[iWord] = tolower (ch);
  678. X          if (iWord < (sizeof (word) - 1))
  679. X        iWord++;
  680. X        }
  681. X
  682. X    }
  683. X    }
  684. X
  685. X}
  686. X
  687. X/***********************************************************************\
  688. X* ftwCallback  * Handle call backs from file tree walking               *                                    *
  689. X\************************************************************************
  690. X*                                               *
  691. X* For each regular file file found by FTW, open it and process the      *
  692. X* contents.                                 *
  693. X*                                    *
  694. X\***********************************************************************/
  695. X
  696. Xint
  697. XftwCallback (const char *pName, const struct stat *pStat, int flag)
  698. X{
  699. X  FILE *pFile;
  700. X
  701. X  if (flag == FTW_F)
  702. X    {                /* is it a file? */
  703. X      if ((pFile = fopen (pName, "r")) == NULL)
  704. X    perror (pName);
  705. X      else
  706. X    {
  707. X      fputs (pName, stderr);
  708. X      fputs ("                        ", stderr);
  709. X      putc ('\r', stderr);
  710. X      processFile (pFile);
  711. X      fclose (pFile);
  712. X    }
  713. X    }
  714. X  return 0;
  715. X}
  716. X
  717. X
  718. X/***********************************************************************\
  719. X* dumpFrequencies * Dump log(2) of frequencies                          *                                    *
  720. X\************************************************************************
  721. X*                                               *
  722. X* Go through the frequency array, converting values to their approximate*
  723. X* log(2) (by looking for the highest order bit set). Then dump out the  *
  724. X* lot to a file "freq.h"                            *
  725. X\***********************************************************************/
  726. X
  727. Xvoid
  728. XdumpFrequencies ()
  729. X{
  730. X  int z = 0, nz = 0;
  731. X  int i;
  732. X  CountType *pCount = (CountType *) count;
  733. X  FILE *op;
  734. X
  735. X  if ((op = fopen ("freq.table", "w")) == NULL)
  736. X    {
  737. X      perror ("freq.table");
  738. X      return;
  739. X    }
  740. X
  741. X  for (i = 0; i < sizeof (count) / sizeof (CountType); i++, pCount++)
  742. X    {
  743. X      int val = *pCount;
  744. X      val == 0 ? z++ : nz++;
  745. X
  746. X      /* Try to chop into the word to work out the magnitude.
  747. X         We're assuming a sensible representation of 'int' here
  748. X      */
  749. X
  750. X      if (val)
  751. X    {            /* map 0 => 0 */
  752. X
  753. X      CountType bit;
  754. X      int hi, lo, med;
  755. X
  756. X      hi = sizeof (CountType) * CHAR_BIT;    /* Top bit number */
  757. X      lo = 0;
  758. X
  759. X      while ((hi > lo))
  760. X        {                /* 2^lo <= val < 2^hi */
  761. X          med = (hi + lo) / 2;
  762. X          bit = (1 << (med)) - 1;    /* lo <= med <= hi */
  763. X          if (val == bit)
  764. X        {
  765. X          hi = med;
  766. X          break;
  767. X        }
  768. X
  769. X          if (val >= bit)
  770. X        lo = med + 1;        /* 2^med <= val < 2^hi */
  771. X          else
  772. X        hi = med;        /* 2^lo <= val < 2^med */
  773. X        }
  774. X      val = hi - 1;
  775. X    }
  776. X
  777. X      fputc (val, op);
  778. X    }
  779. X
  780. X  printf ("\n%d zero, %d not zero\n", z, nz);
  781. X
  782. X  fclose (op);
  783. X
  784. X}
  785. X
  786. X/***********************************************************************\
  787. X* main         *  Parse args and run analysis                           *                                    *
  788. X\************************************************************************
  789. X*                                               *
  790. X* Trundle through the arguments. For each file found, process it.       *
  791. X* For each directory, process it recursively.               *
  792. X*                                    *
  793. X\***********************************************************************/
  794. X
  795. Xint
  796. Xmain (int argc, char **argv)
  797. X{
  798. X  argc--;
  799. X  argv++;            /* Point to first file */
  800. X
  801. X  if (argc <= 0)        /* no args, do stdin */
  802. X    processFile (stdin);
  803. X  else
  804. X    {
  805. X
  806. X      while (argc--)
  807. X    {
  808. X      char *pName = *argv++;
  809. X      int rc;
  810. X
  811. X      /* Note: ftw works as expected if its arg is a regular
  812. X               file as well as a directory */
  813. X
  814. X      if ((rc = ftw (pName, ftwCallback, 12)) != 0)
  815. X        perror (pName);
  816. X    }
  817. X
  818. X    }
  819. X
  820. X  dumpFrequencies ();
  821. X  return 0;
  822. X
  823. X}
  824. END_OF_FILE
  825.   if test 7110 -ne `wc -c <'threes.c'`; then
  826.     echo shar: \"'threes.c'\" unpacked with wrong size!
  827.   fi
  828.   # end of 'threes.c'
  829. fi
  830. echo shar: End of archive 1 \(of 1\).
  831. cp /dev/null ark1isdone
  832. MISSING=""
  833. for I in 1 ; do
  834.     if test ! -f ark${I}isdone ; then
  835.     MISSING="${MISSING} ${I}"
  836.     fi
  837. done
  838. if test "${MISSING}" = "" ; then
  839.     echo You have the archive.
  840.     rm -f ark[1-9]isdone
  841. else
  842.     echo You still must unpack the following archives:
  843.     echo "        " ${MISSING}
  844. fi
  845. exit 0
  846. exit 0 # Just in case...
  847.