Java Trie - Ascii only

Just uploading an Ascii only version, uses a byte instead of a char. Also uses the top bit as an end of word flag so you can not populate it with Ansi (ie 8 bit characters).

https://drive.google.com/file/d/0B_YZvz83_le0alZ1OFNMVW56cWs/edit?usp=sharing

Also probably worth mentioning that this implementation (and the other full 'char' version) will only return the longest match when there are multiple overlapping terms within the Trie. For example a Trie containing "cap", "capitulate", "capitulated" and a search string of "capitulated" would only return the longest, "capitulated".

I haven't implemented the compressed version as it turns out the above version doesn't use that much memory.

Trie - Java implementation

I have ported the C++ code over to Java so I can use it on an android application I am developing. I need to try and reduce the memory footprint and my requirement is only for lower case ASCII so whilst this version uses a Java 'char' I am re-factoring to use a byte (plus re-use some of the top bits). I was also going to try and convert it to a compressed trie. There are a few Java implementations out there and to be honest the only difference with this one is I have used a sorted ArrayList rather than a map within the nodes. I then do a binary search of the list. This probably reduces performance but it should use less memory.

https://drive.google.com/folderview?id=0B_YZvz83_le0VTdDSjF2OU9CTW8&usp=sharing

C++ implementation of a Trie / Prefix Tree

A Trie (http://en.wikipedia.org/wiki/Trie) is a great way to search a stream of text for multiple keywords. It's extremely fast and is a very simple structure to understand. Here is my initial attempt in C++. It is a first cut, not yet fully tested but seems to work. It is case sensitive and will match partial words. The main disadvantage of a Trie is the memory consumption. Each letter requires a node that contains a character / bool and vector so adding words quickly chews up memory.

Here is a link to the source on github:

https://github.com/eskeels/trie

There is just the header file and a main.cpp with some tests. I have also added 2 additional methods, Compress() and ValidateState(). Compress() will recurse through the Trie calling shrink_to_fit() on each of the vectors that are used to store child nodes. ValidateState() performs validation of the nodes. It is only required for testing purposes.

Generating C++ code from a Trie

If you need to search for a small amount of hard coded strings then this might be a good solution. Whilst the Trie is fast you have to contend with the overhead of initialising the Trie data structure and the memory usage. This version of the Trie has a dump() method that will generate a search() function capable of performing a parallel search of all the words in the Trie. Some simple tests have shown this to be considerably faster than using the Trie directly. The generated search() function is pretty ugly and unwieldy but so long as you don't have too many terms it could prove useful.

The prototype of the search method generated is below:

const char * search(const char * pStart,  const char * pbuff, CallbackFunction cf )

pStart is a pointer to the very start of the buff you are search. pbuff is a pointer to the position where you want to search from. Finally cf is a callback function that is invoked whenever a search term is found. A sample showing use of the search function is below:

while( p && (*p != '\0') )
{
p = search(&peterpan[0], p, &myCallback );
count++;
}

The callback is of the form:

int myCallback(const char * pStart, const char * pbuff, const char * resultString, const char * position)

pStart / pbuff are as per the search() method. resultString is a NULL terminated string containing the search term that has been found. position is a pointer to the last character of where it was found. The return type is currently ignored.

The code is below. It is the same as the other Trie code example however it has the dump() methods added and a tweak to track the size of the largest term in the Trie.

https://github.com/eskeels/trie_code_generator

Sample code

An example callback function. It uses std::distance() to work out the offset.

int myCallback(const char * pStart, const char * pbuff, const char * resultString, const char * position)

{

std::cout << "Found word :" << resultString << std::endl;

if (pStart && position)

std::cout << "At position :" << std::distance(pStart, position) << std::endl;

return 0;

}

// This is the search() function output from the call to dump().
typedef int (CallbackFunction)(const char * pStart, const char * pbuff, const char * resultString, const char * position);

const char * search(const char * pStart,  const char * pbuff, CallbackFunction cf )
{
  const char * p = pbuff;
  const char * pRet = NULL;
  const size_t maxWordLen = 7;
  while(*p)
  {
  switch(*p){
  case 'c':
    switch(*(++p)){
    case 'a':
      switch(*(++p)){
      case 't':
      // found a word:cat Store pointer to last character of where it was found.
      pRet=p;
      cf(pStart, pbuff, "cat", p);
        switch(*(++p)){
        case 's':...

...

...

   int main(int argc, char* argv[])
  {
      Trie<char> t;
      std::map<const void *,std::string> dictionary;
      std::vector<SearchResult<char> > searchResults;

      AddWord<char>("cat", t, dictionary);
      AddWord<char>("cats", t, dictionary);
      AddWord<char>("peter", t, dictionary);
      AddWord<char>("wendy", t, dictionary);
      AddWord<char>("hook", t, dictionary);
      AddWord<char>("hooks", t, dictionary);
      AddWord<char>("party", t, dictionary);
      AddWord<char>("pillows", t, dictionary);
      t.dump();
      return 0;

}

// Run once calling the dump() function and then capture the output.

std::ifstream myfile ("c:\\Users\\soswin\\peterpan.txt");

std::string peterpan;

std::string line;

if (myfile.is_open())

{

while ( getline (myfile,line) )

{

peterpan.append(line);

}

myfile.close();

}

while( p && (*p != '\0') )

{

p = search(&peterpan[0], p, &myCallback );

}

}

X86 assembly with GAS on Windows

I've been reading "Professional Assembly Language" by Richard Blum. The book gives a good overview of Intel architecture and takes you through from very basic samples. The sample assembly programs in the book assume you are on Linux and are using the gnu assembler however it is simple enough to get working on Windows. I do have a Linux box but I wanted to try the sample programs on my laptop which is Windows 7 (I couldn't get Ubuntu stable, too much hassle with the WiFi card and also the battery life is way better with Windows). Firstly download MinGW from:

http://www.mingw.org/

This will provide you with the Gnu Assembler (as.exe under MinGW\bin). Now most of the samples will run fine up-to the last part where they try to output to console. The book gives the following instructions to output a string:

movl $4, %eax
movl $1, %ebx
movl $output, %ecx
movl $42, %edx
int $0x80.

This is from Page 80 of the book. EAX contains the system call value, EBX is the file descriptor to write to, ECX is the start of the string and EDX is the length. Now to do the same on Windows we are going to utilise a Win32 system call from the kernel32.dll:


pushl $-11
call _GetStdHandle@4
mov %eax, handle
pushl $0
pushl $written
pushl $42
pushl $output
pushl handle
call _WriteConsoleA@20


pushl $0
call _ExitProcess@4

This is equivalent to the following C code:


handle = GetStdHandle(-11);
WriteConsole(handle, &msg[0], 13, &written, 0);
ExitProcess(0);

I got the above from this site http://www.cs.lmu.edu/~ray/notes/x86assembly/. Its a very useful page showing you how to call C libraries / system calls on Windows and Linux.

I will now apply the above to a sample from the book. The sample program on page 77 will call the CPUID instruction and output the result. The code below is the same as the sample bar the final output. To build this you need to link in the kernel32.dll by issuing the ld command after calling the assembler:


as -o cpuid.o cpuid.s
ld -o cpuid.exe cpuid.o -lkernel32

Contents of cpuid.s:

.section .data

output:
  .ascii "The processor vendor ID is 'xxxxxxxxxxxxx'\n"
handle: .int 0
written: .int 0


.section .text
.globl _start
_start:
  movl $0, %eax
  cpuid
  movl $output, %edi
  movl %ebx, 28(%edi)
  movl %edx, 32(%edi)
  movl %ecx, 36(%edi)
  pushl $-11
  call _GetStdHandle@4
  mov %eax, handle
  pushl $0
  pushl $written
  pushl $42
  pushl $output
  pushl handle
  call _WriteConsoleA@20


  pushl $0
  call _ExitProcess@4

Installing OpenLDAP on Windows 7

The following is a simple guide to installing OpenLDAP for the purpose of trying it out in a dev environment. The installation is on Windows 7. I've written this up as it is something I have to do infrequently and so forget the detail each time. The other online tutorials never seem to go as far as connecting an LDAP browser to the directory server you have just installed.

Download the MSI from http://www.userbooster.de/en/download/openldap-for-windows.aspx

The installation notes are http://www.userbooster.de/en/support/feature-articles/openldap-for-windows-installation.aspx. The LDAP requires a database repository, the "Backend Configuration"dialog allows you to choose from BDB, LDAP, LDIF, SQL-Server:

The easiest option is the LDIF backend as this is merely a file directory of LDIF files

Running the LDAP

You can either start with windows service or just run the "run.cmd" file that is provided in the C:\Program Files (x86)\OpenLDAP\run folder. I prefer to just run the cmd file as its not something I need running all the time and with a command console any errors are displayed immediately. Launch "run.cmd" as Administrator (right click the icon and select "run as Administrator"). If you have windows firewall running it will prompt you to allow it access. Select the "Private networks, such as my home or work network" option. You need to leave that command window open, it is the Open LDAP process. To stop Open LDAP just close the window.

Connect an LDAP browser

Once installed the cn=Manager,dc=maxcrc,dc=com user is available to bind with but the dc=maxcrc needs adding before you can successfully connect an LDAP browser. OpenLDAP has command line utils in the ClientTools folder to allow you to perform this. CD to this folder (c:\Program Files (x86)\OpenLDAP\ClientTools) then paste the following command:
ldapmodify.exe -a -x -D cn=Manager,dc=maxcrc,dc=com -w secret -f ..\maxcrc.ldif


If successful you'll see the following output:


adding new entry "dc=maxcrc,dc=com"


adding new entry "ou=People,dc=maxcrc,dc=com"

You now have an organisational unit called "People" under the dc maxcrc. This is somewhere you can start creating new user objects (or whatever type of object you want.) Now we are going to connect the LDAP browser Jxplorer. Download and install from this site http://jxplorer.org/downloads/users.html

There are no configuration options during the install. Run Jxplorer and then from the File menu select connect. You will see and "Open LDAP/DSML Connection" dialog. Enter the details as follows:

and then click ok. After a short pause (5-10 seconds on my laptop but it is only an i3 1.33ghz) and the explorer pane on the left should be populated with a small tree structure:

We are now going to add a new user. Select the People Organisational unit then type Ctrl+n. Select inetorgperson from the "Available classes" window and enter cn=user1 for the RDN:

Click the OK button. You will now see the "Table Editor" in the right hand pane. The fields in bold are mandatory for the given object class. We need to populate the sn field before we can add our new user:

enter a surname and then press the "Submit" button at the bottom of the pane. Our user has now been added to the directory server. If you check this folder "C:\Program Files (x86)\OpenLDAP\ldifdata\dc=maxcrc,dc=com\ou=people" you will see a new file created called "cn=user1". Do not tweak these files direct, use the LDAP browser.