home *** CD-ROM | disk | FTP | other *** search
/ ProfitPress Mega CDROM2 …eeware (MSDOS)(1992)(Eng) / ProfitPress-MegaCDROM2.B6I / TEXT / UTILITY / COGNATE.ZIP / COGNATE.DOC next >
Encoding:
Text File  |  1991-12-02  |  8.2 KB  |  174 lines
  1.  
  2.  
  3.                           COGNATE
  4.  
  5.                        an apparently
  6.                 wonderfully useless program
  7.                  implementing an algorithm
  8.  
  9.                              by
  10.  
  11.                       Jacques B.M. Guy
  12.  
  13.               Artificial Intelligence Systems
  14.          Telecom (Australia) Research Laboratories
  15.  
  16.  
  17.  
  18.  
  19.  
  20.  
  21. WHAT IS "COGNATE"?
  22.  
  23. COGNATE is the implementation of a prototype algorithm for identifying
  24. related words across languages.
  25.  
  26. My ultimate purpose in developing COGNATE was to take a first step towards
  27. solving a far more interesting, and difficult, problem of automatic
  28. machine translation: given a bilingual text, find the rules for
  29. translating from either language into the other.
  30.  
  31. Given the same list of words in two different languages, COGNATE will
  32. determine which words are likely to be regularly derivable from each
  33. other, and which are not. The longer the list, or the more closely related
  34. the two languages are, the better the performance of COGNATE. For instance,
  35. suppose that you have typed into a file 200 words in English (one per
  36. line), and in another file the same 200 words, in the same order, in German
  37. (again one per line). English and German are fairly close languages. Given
  38. these two files, and no other information whatsoever, COGNATE will be able
  39. to tell for instance that English "TWENTY" and German "ZWANZIG" are almost
  40. certainly derivable from each other, and so are English "HONEY" and German
  41. "HONIG"; but it will also tell you that English "HORSE" and German "PFERD"
  42. are not so related. COGNATE will also tell you, when comparing "TWENTY"
  43. with "ZWANZIG", that English "T" corresponds to German "Z".
  44.  
  45. Because of the very nature of the algorithm, you may encypher each file
  46. using a simple-substitution code, without causing COGNATE to be confused.
  47. For instance, if you have encoded the English data by shifting one letter
  48. forward (so that "TWENTY" becomes "UXFOUZ") and the German data by shifting
  49. one letter backward (so that "ZWANZIG" becomes "YVZMYHF"), COGNATE will
  50. still able to tell that "UXFOUZ" and "YVZMYHF" are related, and that
  51. "IPSTF" ("HORSE") and "OEDQC" ("PFERD") are not.
  52.  
  53. I thought up the algorithm behind COGNATE around 1981, and implemented it
  54. first in Simula 67 on a DEC KL10. Then, as a self-inflicted challenge
  55. which I did not expect to win, I tried to translate it into Turbo Pascal,
  56. to run on my Kaypro II. It worked. On a Kaypro II, it would take COGNATE 40
  57. seconds to analyze two files each containing 200 words, and find which were
  58. related and which not. On a 386DX running at 33MHz, the same operation
  59. looks as if it were instantaneous.
  60.  
  61.  
  62. HOW DO I RUN "COGNATE"?
  63.  
  64. All you need as input for COGNATE are two or more plain ASCII files, each
  65. containing the same words, in the same order, but in different languages.
  66. If the words are not in the same order, COGNATE will become hopelessly
  67. confused and incapable of finding related words (with a huge bit of very
  68. bad luck, it may even attempt dividing by zero somewhere). I have typed in,
  69. for demonstration purposes, 200 words in English, in German and in Dutch
  70. into three files named "ENGLISH", "GERMAN" and "DUTCH".
  71.  
  72. Just type "COGNATE". You will be asked for the name of the first file.
  73. Answer, say, ENGLISH. Then for the name of the second file. Answer, say,
  74. DUTCH. If you have given the names of non-existent files COGNATE will tell
  75. you which ones it could not find, and ask you again for file names. Just
  76. pressing RETURN, without typing in any name, will return you to DOS.
  77.  
  78. Given those two file names, COGNATE will read the data they contain and
  79. start working on it. How long will it take? It all depends on the size of
  80. the files. With the ready-to-go files provided, and if you are using a 386
  81. machine, you won't have the time to count "zero, one". From then on, you
  82. are on your own, just follow the prompts on the screen. They are as
  83. self-explanatory as I could make them in one afternoon of slaving at
  84. translating the original Kaypro II, Turbo Pascal 2 implementation to Turbo
  85. Pascal 5.5, while trying to tweak some more accuracy and user-friendliness
  86. out of it. The screen will show the first word pair that COGNATE had read
  87. out of the two files you gave it to work on. First, in the form of the
  88. matrix it uses to evaluate whether there were related or not. This matrix
  89. contains probabilities (in whole percentage, to save space) whether any two
  90. letters of those words show evidence of cross-correlation. Under the
  91. matrix, the words are repeated, with COGNATE's opinion whether the
  92. correlations are strong enough to consider them related, and precisely how
  93. they correlate. At the bottom of the screen, you see a primitive menu:
  94.  
  95. N(ext), P(revious), J(ump), M(inimum match), O(ther pass), Q(uit) ?
  96.  
  97. Just type the first letter: N, P, J, M, O, or Q.
  98.  
  99. N(ext) takes you to the next word pair.
  100. P(revious) takes you to the previous pair.
  101. J(ump) has COGNATE prompt you for the number of the word pair you want to
  102.      jump to. A hint: the words are arranged alphabetically in the English
  103.      list.
  104. M(inimum) has COGNATE prompt you for the minimum probability of correlation
  105.      between two letters for that correlation to be considered in its
  106.      computations.
  107. O(ther pass) has COGNATE carry the necessary computations to move to the
  108.      next pass of the algorithm. If you are already in the second pass,
  109.      it returns you to its first-pass state.
  110. Q(uit) will ask you for confirmation before returning you to DOS.
  111.  
  112. You can also use the following keys:
  113.  
  114. RETURN and Down-Arrow have the same effect as N(ext).
  115. Up-Arrow has the same effect as P(revious).
  116. PgUp moves 20 word-pairs back.
  117. PgDn moves 20 word-pairs forward.
  118. Home takes you to the top of the list.
  119. End takes you to the bottom of the list.
  120.  
  121. COGNATE uses a two-pass algorithm. Results obtained during the second pass
  122. are always better than those obtained in the first (but surprisingly
  123. only marginally so sometimes). If you compare German with English, using
  124. the files provided, note how, in the first pass, COGNATE is pretty certain
  125. that "BEACH" and "STRAND" are related, and how, in the second pass, it has
  126. reversed its opinion.
  127.  
  128.  
  129. HOW ABOUT TESTING "COGNATE" ON OTHER LANGUAGES WITH OTHER WORDS?
  130.  
  131. When typing in those three sample files I did not even bother to use
  132. phonetic spelling, which would probably have made things easier for
  133. COGNATE. Just for fun, you may try to create another English file,
  134. containing the same words (in the same order, remember!) but in a phonetic
  135. spelling of your invention, and see if COGNATE can correlate your phonetic
  136. spelling with traditional English spelling.
  137.  
  138. There is no need to use the particular 200 words I have used. You may use
  139. any other words, in any number, as long as the same words appear in the
  140. same order in each file, one per line (never mind the language they're
  141. in), and as long, of course, as they'll fit in your computer's memory. Try
  142. for instance comparing Spanish, Italian, French, and Latin. Try comparing
  143. Polish, Ukrainian, Slovenian, and Russian. Comparing Finnish, Hungarian,
  144. and Turkish, however, will get you nowhere: for even though all three are
  145. related, their relationship is so distant that COGNATE will not find enough
  146. regular correspondences to work on. An amusing experiment would be to
  147. compare Esperanto with some European languages.
  148.  
  149.  
  150. NOW FOR THE USUAL LEGAL MATTERS
  151.  
  152. The usual copyright notice applies. But in particular:
  153.  
  154. The executable file must be distributed with the present documentation file
  155. as is, including the closing acknowledgement.
  156.  
  157. COGNATE.EXE, this documentation file, and the three sample wordlists that
  158. ought to come with it are distributed free.
  159.  
  160. For those tempted to dissassemble the code to find out what makes COGNATE
  161. tick, a piece of advice: a library search will get you what you are after
  162. infinitely more easily. Look for something around, say, 1983-85. The
  163. present algorithm is fundamentally the same, except for the choice of the
  164. objective functions. Alternately, observing its behaviour will tell you a
  165. great deal, perhaps even more than reading the description of the original
  166. algorithm.
  167.  
  168.  
  169. ACKNOWLEDGEMENT
  170.  
  171. The permission of the Executive General Manager of the Research
  172. Laboratories of Telecom Australia to distribute this material
  173. is gratefully acknowledged.
  174.