ngrams are a rather classical instrument in Natural Language Processing (NLP) applications.
&ngramj; is a Java based library containing two types of ngram based applications. It's major focus is to provide robust and state of the art language recognition (or language guessing how some call it more correctly). Both types are meant to be embedded into larger applications.
Language recognition is not the only NLP application of ngrams and &ngramj; can be used as a building block in all kinds of differing applications. However Langugage recognition was my major application and therefore &ngramj; is somewhat streamlined for this.
Once you are in a program and treat Strings and other kinds of character sequences, &cngram; is the only reasonable way to go.
The &cngram; library has been developed under consideration of multithreading and performance requirements. &cngram; has also a language recognition mechanism which (to some extend) successfully recognizes mixed language documents.
Caution: For historical reasons &ngramj; sometimes refers to the (older) byte based ngrams excluding the newer addition of &cngram;. I'm sorry about the confusion.
There are alternative Java implementations of n-Grams.
Apart from language/encoding recognition one can do more things with ngrams. None of them have been precanned into &ngramj; however.
Lets assume, you want to run &ngramj;. Developer information is elsewhere.
The process is very easy
It is assumed, that you have a recent (1.4+) Java environment on your computer. This is because, the programm has been precompiled for Java 1.4. At least the (older) byte-&ngramj; part has been carefully coded and tested to run with Java 1.1 when you add the repackaged collections-jdk1.2.jar which once kicked arround in the internet. I lost track of it. I'm not aware if these repackaged collections are a legal problem, but I'm also not sure if really anyone needs Java 1.1 anymore.
If you don't have Java, please, download java here.
&ngramj; currently comes in two different packages (VVV is some lengthy version information):
ngramj-VVV.bin.zipngramj-VVV.all.zipFor the actual download go to the Sourceforge Download Page.
Run either byte &ngramj; or character &cngram; Here are some common cases.
Usage is very simple.
cngram.jar from the binary download.cngram.jar on the commandline. This is an self executing jar and this works on JRE installations from version 1.2. If your JRE is misconfigured use the equivalent call java -jar cngram.jarcngram.jar -lang2 YOUR_FILENAME FILE_ENCODING-lang uses the old algorithm, -lang2b calls the new algorithm twice to demonstrate speedup.)For historical reasons &ngramj; does not have such a simple commandline like &cngram;.
Unpack ngramj.jar from the binary download.
The call for language and encoding determination is.
ngramj.jar YOUR_FILENAME
Other calls are:
java -classpath ngramj.jar de.spieleck.app.ngramj.phoner.Phoner A_PHONE_NUMBER
java -classpath ngramj.jar de.spieleck.app.ngramj.lm.LMWriter TEXT_SAMPLE PROFILE_NAME
An ngram is a (short) sequence of atoms like bytes, characters, words or whatsoever. In this settings we only care about bytes or characters. Though ngrams of words are a more recent technology.
As it turns out many properties of a underlying text (for example language, style, but even thematic focus) have a statistical stable impact on the ngram profile of this text. The ngram profile is the (statistical) distribution of ngrams, that is how often a certain ngram appears in a certain sequence.
Once you know you are hunting for a set of properties which is well reflected by a set of corresponding profiles, you can setup an automated search for these properties by the following steps.
The above description is far from being an algorithm. Actually there has to be some careful investigation if a property is refleced by ngrams profiles. You have to set up reference profiles from (as large as possible) reference suits of texts with that property. And you have to precise what you mean with closeness of two ngram profiles.
&ngramj; only cares about byte or character based ngrams. While there are other applications, the major application of this is the recognition of the language of a document. This is a somehow easier part of ngram application, for several reasons. To name two:
The &cngram; part of &ngramj; however uses a somewhat more elaborate notion of competitive ngram closeness which in the end assigns language percentages to a piece of text. This measurement is good enough that not only texts in one language but also texts with two major languages have been successfully classified with &ngramj;!
&ngramj; is a very basic library. It is solely based on the following base technologies:
Since &ngramj; is more about algorithms, datastructures and some math there is no need to use other libraries. Java is more than enough. However we might add some log4j or so in an update, to ease error finding.
Well of course it is a Java project. But beside an arbitrary JRE 1.2 or later (JRE 1.1 probably works when you have the plugin Collection Classes ) following things are (more or less) necessary for &ngramj;:
Nothing, unless you want to run the
Sourceforge provides every project with forums. Just go to the &ngramj; Forum page.
There is also a developer list. Both list are no traffic at time of this writing. Fell free to join.
Please help us and contribute, whatever you did with &ngramj;. Or even whatever you would like to do with it.
Please contact us via our SourceForge pages.
There is also Sourceforge SVN repository for &ngramj;.
This will not be interesting to you, unless you consider doing programming work arround or in &ngramj;.
If you first want to build &ngramj; yourself you might want to look to the &ngramj; build section.
Note: Currently &ngramj; has been developed to the point, where it is useful for my initial task and some other simple applications. There might be entirely different tasks to be accomplished with &ngramj;
Please feel free to join or contribute!
There are two basic download formats
available. If you want to inspect the code, for fun or to
improve it, the ...-all.zip is for you!
Depending on the version of the zip file you downloaded you will have some or all of the below files:
ngramj.jarcngram.jarlib/doc/src/build.xmlbuild.propertiesbuild.xml file.build.numberChangeLog.txtLICENSE.txtREADME.txtREADME-license.txtThis still has to be written.
General policy. &ngramj; provides a working ant file which does not use any special libraries unless you try to package distributions.
Here is the JavaDoc main index.
Be sure you have read the principles page, this should help you figuring what is going on.
Recommended start for reading classes:
&ngramj; is Open Source published under the so called LGPL. This is:
Copyright (C)
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
Also add information on how to contact you by electronic and paper mail.
You should also get your employer (if you work as a programmer) or your
school, if any, to sign a "copyright disclaimer" for the library, if
necessary. Here is a sample; alter the names:
Yoyodyne, Inc., hereby disclaims all copyright interest in the
library `Frob' (a library for tweaking knobs) written by James Random Hacker.
, 1 April 1990
Ty Coon, President of Vice
That's all there is to it!
]]>
I document this, cause this is IMHO the hardest thing to determine ad hoc given a bunch of more or less quality code.
I use to be a performance geek. (byte) &ngramj; wasn't that bad in it times, but its basic design is still Java 1.1.8 some decisions are possibly to revisit after such a long time.
&cngram; contains a new mechanism to be efficient at task which require many documents to be matched against a set of profiles.
This technique is based on (slightly costly) preprocessing of a set of profiles. Therefore the commandline version is actually slightly slower. But after preprocessing new texts can be classified without additional memory and without actually ever creating any ngram objects. The algorithm immediately competitively scores the text against the given sample profiles. It is needs time O(textlength * number of languages). With a relatively small proportional factor. Whereas the classical method to first convert a given a text into a profile, costs memory proprotional to the different ngrams in the text. And only afterward this profile has to be matched against prescribed profiles which costs time depending on the number of profiles and the number of total profiles involved. If you have very many sample languages and very short texts, the classical method might be superior to the new one.
While the new technique was mainly implemented to achieve high performance in tasks where many documents have to be language classified, it turns out that it can provide different, probably better results:
To avoid memory allocations all ngram scoring has to be "on the fly" based on a currently seen short segment of text. This restrictrion actually allows for some "context" to creep into evaluation. That is a actual ngram can score different depending on preceeding ngrams. This does actually happen. Look at the word "question". When it is analyzed alone it recognized as being French with some tendencies to Italian, Spanish and English. However analyzed as part of the phrase "To be or not to be, this is the question" the preceeding strong English context scores it as being English with a littlebit of French.
Note the new technique of profile preprocessing could be easily ported back to (byte) &ngramj;, but this hasn't been done yet.
The competitive sampling procedure relies on a fast implementation of ternary search tries. This trie is "reentrant" in the sense, that you can proceed descending the tree after you found a match.
E.g. say we are parsing the String quest and we are currently proceeding the t. Then we have to look at the following ngrams in sequence: the 1-gram t, then the 2-gram st, then the 3-gram est. In a search trie of reversed ngrams we can first determine the leaf for t and then proceed into the subtrees for first ts and second tse, thus the lookup of all ngrams ending up with t can be done by only one traversal down the search trie.
This is a library and the executables are mere demos and samples how to embed the library.
Other information arround the &ngramj; project.
See subcategories on the left hand side.
Just that it doesn't get lost :-)
There seem to be two contenders in the Open Source Java sphere.
After all, if you need something additional, you might consider joining forces and work with &ngramj;.
Outside the Java universe there are plenty of other implementation in whatever languages (C, Perl, Python and more).
Well this is some advertisement. Other open source projects where we are major contributors are:
<advertisement>
Well, it is my domain and that is why I use the namespace
for my projects. spieleck.de
is an semi experimental server to quickly try out ideas, some
of them might survive or even go productive.
</advertisement>
Well, and for those of you who do not speak German: Spiel is game and Eck is corner and that that what it all was meant to be: A place to play and toy arround on the net.