| 1 |
AikSaurus 0.11 ==> 0.12 ToolSet Readme File |
| 2 |
----------------------------------------------------------------------- |
| 3 |
|
| 4 |
Many apologies in advance for the severe disarray of this toolset. |
| 5 |
|
| 6 |
Introduction |
| 7 |
============ |
| 8 |
|
| 9 |
This is a collection of utility programs which were used in the |
| 10 |
transition from AikSaurus 0.11's flat database style to the new, |
| 11 |
bipartite-graph model used in AikSaurus 0.12. |
| 12 |
|
| 13 |
The transition is an expensive process computationally, and a |
| 14 |
delicate process to do well. My results are certainly not |
| 15 |
optimal, so for those (if any) who are interested in playing |
| 16 |
with the problem themselves, these tools might come in handy. |
| 17 |
You may want to expand onto them or refine them in some way. |
| 18 |
|
| 19 |
I would *highly recommend* reading the paper "Building a Better |
| 20 |
Mousetrap: Architectural Changes behind AikSaurus 0.12" and |
| 21 |
comprehending it before you try to do a whole lot with these |
| 22 |
things. It will give you a good feel for what these programs |
| 23 |
do and what good ways to use them are. |
| 24 |
|
| 25 |
These tools are almost exclusively written in C++. They rely |
| 26 |
heavily on the power of the standard template library, and thus |
| 27 |
an understanding of the STL is nearly prerequisite to trying to |
| 28 |
modify much of the code. |
| 29 |
|
| 30 |
You will need a relatively powerful machine to do much with |
| 31 |
this code. It is not uncommon for these programs to allocate |
| 32 |
up to around 150 megs of memory, and keep that memory allocated |
| 33 |
for a good hour or two while they work. You should NOT run |
| 34 |
these programs on shared computers/servers without permission |
| 35 |
from your systems administrator. While virtual memory is a |
| 36 |
wonderful thing, you want to avoid it because it will severly |
| 37 |
slow down these operations which are computationally expensive |
| 38 |
anyway. |
| 39 |
|
| 40 |
In extreme cases, some of these programs can take literally |
| 41 |
hours to complete. For example, running MergeEngine against |
| 42 |
30,000 words took my Athlon 650 a little over 9 hours. |
| 43 |
MergeEngine is an O(n^2) operation and a slow one at that, |
| 44 |
so it should be used with caution on large data sets. |
| 45 |
|
| 46 |
|
| 47 |
Explanation of Contents |
| 48 |
======================= |
| 49 |
|
| 50 |
./gen_pms |
| 51 |
|
| 52 |
Contains utilities to create the preliminary meaning |
| 53 |
set families. This code is the roughest you'll find |
| 54 |
here because once I had the initial preliminary set, |
| 55 |
there wasn't a whole lot of reason to generate it |
| 56 |
again. |
| 57 |
|
| 58 |
You will need to create a symlink to ./src/thesaurus.in |
| 59 |
named "thesaurus.in" in this directory in order for any |
| 60 |
of the programs to work. |
| 61 |
|
| 62 |
I honestly don't know what a lot of the files in this |
| 63 |
directory were ever used for. There's no nice make |
| 64 |
system, you'll have to compile the programs by hand. |
| 65 |
The source is the only documentation. Sorry. |
| 66 |
|
| 67 |
|
| 68 |
./src |
| 69 |
|
| 70 |
Contains all the source code for the main refinement |
| 71 |
programs. This includes the merge engine and so forth. |
| 72 |
|
| 73 |
Also includes programs used to create the final |
| 74 |
implementation files. |
| 75 |
|
| 76 |
Also includes the file "thesaurus.in" -- a very slightly |
| 77 |
modified Moby thesaurus file. (24 MB) |
| 78 |
|
| 79 |
You should run "make" in the source directory before |
| 80 |
too long. |
| 81 |
|
| 82 |
|
| 83 |
./old_data |
| 84 |
|
| 85 |
Contains a bunch of my failed attempts at creating a nice |
| 86 |
set of data. |
| 87 |
|
| 88 |
Interesting files: |
| 89 |
|
| 90 |
./old_data/d.initial/m.0 |
| 91 |
initial preliminary meaning sets file with 66683 words. |
| 92 |
unaltered output from ./gen_pms/engine program. |
| 93 |
|
| 94 |
./old_data/d.initial/m.1 |
| 95 |
same as m.0, but with subset elimination reducing about |
| 96 |
half of the sets. This is my recommended starting place |
| 97 |
for you if you want to play with data. It's the most |
| 98 |
usable while-still-being-pure meanings file available |
| 99 |
out of the box. |
| 100 |
|
| 101 |
|
| 102 |
./datagen |
| 103 |
|
| 104 |
Works with ./src in order to convert a finalized meanings.text |
| 105 |
file into implementation form. Creates words.dat, meanings.dat, |
| 106 |
and MeaningsHash.h which are used in the implementation. |
| 107 |
|
| 108 |
This is the final step once you get your thesaurus data assembled. |
| 109 |
Just throw it into here, run make, and then copy those files into |
| 110 |
the Aiksaurus implementation directory, rebuild Aiksaurus, and you |
| 111 |
should have a new thesaurus based on your data files. |
| 112 |
|
| 113 |
|
| 114 |
./meanings.text |
| 115 |
|
| 116 |
This is what I came up with for my meanings file before throwing |
| 117 |
it into the implementation. |
| 118 |
|
| 119 |
|
| 120 |
Programs and Conventions |
| 121 |
======================== |
| 122 |
|
| 123 |
You will probably find that you are generating a lot of files, |
| 124 |
possibly in an interative fashion. If you want to keep your |
| 125 |
previous files while iterating (which is nice to be able to |
| 126 |
look back on and see how you've progressed), I found that some |
| 127 |
naming conventions on the files were useful. |
| 128 |
|
| 129 |
|
| 130 |
Generating Meanings Files |
| 131 |
------------------------- |
| 132 |
|
| 133 |
The original input file is a slightly modified Moby Thesaurus |
| 134 |
File, which you will find is named "thesaurus.in". This file |
| 135 |
is used in many of the programs to calculate various ratios |
| 136 |
and is hence included in the distribution. It's also 24 megs, |
| 137 |
which is one of the many reasons the toolset is so huge. |
| 138 |
|
| 139 |
The program "engine" can convert the thesaurus.in file into a |
| 140 |
meanings file. It is a slow program and took slightly over an |
| 141 |
hour to run on my Athlon 650. Your times should differ from |
| 142 |
this figure based on your system's speed, and also based on |
| 143 |
what smallmerge-ratio you decide to use for your engine run. |
| 144 |
The default is .5 and is hard-coded in, so you will have to |
| 145 |
change it in the source code if you want to use a new value. |
| 146 |
Moreover, engine is the least mature program in the toolset |
| 147 |
and so maybe I'll work on it a little later, but engine isn't |
| 148 |
used very often so it's kind of a why-pursue-that sort of deal... |
| 149 |
|
| 150 |
Anyway, I named my initial meanings file m.0 and suggest that |
| 151 |
you do the same. You'll find that as you crop out meaning sets |
| 152 |
you might want to compare what you've done at each step. It is |
| 153 |
easy to do this if you name each iteration m.1, m.2, m.3, etc., |
| 154 |
and the other programs in the toolset will prompt you for |
| 155 |
"meaning files" and suggest (m.#) as the file name. |
| 156 |
|
| 157 |
|
| 158 |
Cropping and Merging Meanings |
| 159 |
----------------------------- |
| 160 |
|
| 161 |
Most of the time you will be very interested in reducing the |
| 162 |
size of your meanings file. You can do this through two primary |
| 163 |
ways: |
| 164 |
|
| 165 |
1) removing meaning sets entirely |
| 166 |
2) merging together existing meaning sets |
| 167 |
|
| 168 |
The "MergeEngine" program can do merging based on the smallmerge |
| 169 |
and also does subset elimination (set ratio=1 to do pure subset |
| 170 |
elimination with no merging). |
| 171 |
|
| 172 |
Note that MergeEngine is extremely computationally expensive and |
| 173 |
you should not try to run it on files of much more than 30,000 |
| 174 |
sets if you want it to complete within a day. You can run it in |
| 175 |
an iterative fashion using fixed size blocks, which will give you |
| 176 |
drastic reductions at first but then will see decreasing returns |
| 177 |
on subsequent runs of same sized blocks. |
| 178 |
|
| 179 |
|
| 180 |
Generating Words Files from Meanings |
| 181 |
------------------------------------ |
| 182 |
|
| 183 |
Once you have a meaning set file, you may wish to extract a list |
| 184 |
of all words in the file. The "ExtractWords" program can do |
| 185 |
this for you. I tend to name the words files with a (w.#) filename |
| 186 |
so that you can easily tell which meaning file they were created |
| 187 |
from. "ExtractWords" is relatively fast and should complete in |
| 188 |
under a minute on most data sets. It is O(n) where n is the total |
| 189 |
number of _words_ in the meanings file. |
| 190 |
|
| 191 |
With a words file extracted, you can created a Linked Words File |
| 192 |
which contains entries such as: |
| 193 |
fool 102 394 2933 3948 |
| 194 |
|
| 195 |
Where these numbers refer to meaning sets that fool appears in. |
| 196 |
The "LinkWords" program can do this for you. I named my linked-words |
| 197 |
files "link.#" where # corresponded to the meanings files, words files, |
| 198 |
etc. LinkWords is relatively quick and should execute in a few |
| 199 |
minutes for most data sets. |
| 200 |
|
| 201 |
|
| 202 |
Generating Random-Word Reports |
| 203 |
------------------------------ |
| 204 |
|
| 205 |
With a linked words file, you can generate RandomWords reports. These |
| 206 |
are really useful in seeing how you're doing. The first thing you need |
| 207 |
to do is create a file with a few random words in it, just list one |
| 208 |
per line. Now, run the RandomWords program and it will let you create |
| 209 |
an HTML report that tells you how many links those words have, shows |
| 210 |
you the sets, and calculates some statistics about those sets. These |
| 211 |
let you spot trends visually in the data and see where improvements |
| 212 |
could be made. In particular, the observation that large sets tend to |
| 213 |
have low link ratios was almost instantly obvious once I saw one of |
| 214 |
these random-word reports, whereas before it didn't even cross my mind. |
| 215 |
They can be a good source for inspiration when trying to think of |
| 216 |
better ways to extract meanings, combine sets, etc. |
| 217 |
|
| 218 |
A word of warning, "RandomWords" is a slow program. Its speed will be |
| 219 |
based on the number of words in your random words file and the number of |
| 220 |
meaning sets that each of those words belongs to. |
| 221 |
|
| 222 |
|
| 223 |
|
| 224 |
Link Ratios and Link Ratio Based Analysis |
| 225 |
========================================== |
| 226 |
|
| 227 |
You should read over the directLinkRatio and returnLinkRatio |
| 228 |
parts of the paper and become familiar with these measurements, |
| 229 |
since they give you an added weapon to use to identify "bad" |
| 230 |
meaning sets. |
| 231 |
|
| 232 |
Probably the most useful aspect of these ratios is that a |
| 233 |
meanDirectLinkRatio / meanReturnLinkRatio are very good at |
| 234 |
indicating how good the interlinking is between the synonyms |
| 235 |
of a set. In addition, since they boil down to an actual |
| 236 |
number you can use them to very quickly sort out by arbitrary |
| 237 |
criteria, for example "show me only the sets with mdlr+mrlr < .2" |
| 238 |
will give you very weakly linked sets which you can then choose |
| 239 |
to split up, discard, or what have you. |
| 240 |
|
| 241 |
The program "RatioAdder" will take a meanings file and change |
| 242 |
it so that the first two entries are the mdlr and mrlr of the set, |
| 243 |
respectively. This is a slow program and may take a couple of |
| 244 |
hours to complete if pitted up against a large meanings file. |
| 245 |
However, it does provide you the ability to specify only a block |
| 246 |
of the file to process at a time, and does not require iterations |
| 247 |
like MergeEngine. |
| 248 |
|
| 249 |
|
| 250 |
|
| 251 |
|
| 252 |
_______________________________________________________________________ |