Use a binaryincluded text file

[netmaestro]

Hello. I hope someone can help me. Here is what I want to do:

I have a word game which uses as its dictionary a text file containing 170,000 words. It is around 1.7 mb in size and is sorted. I would like to include the text file in my exe and search it quickly to see if a word exists in it or not. I imported the text into an Access database and was disappointed in the size of the resulting file. It was at least 9 mb in size. Too big. Ideally what I think I'd like to do is include the text file in my program with IncludeBinary and open it for reading as though it were a file on disk. I'm sure it can be done but my searches through the forum were fruitless. Anybody able to show me the way?

[Dare2]

Hi netmaestro,

Re the access DB, have you tried to compress it? Adding records in sorted order to the mdb tends to be the worst in terms of speed (during build) and size, but compressing can take size down quite a bit.

With regards the text file, how is it organised? Is it indexed in some way? Is it just a word list, eg:

• A
  Aardvark
  Able
  Ace

How the memory "file" access is handled will depend a bit on this. If it is not indexed then a sequential search is simple but may be a bit slow and building a small index might help.

Finally, Paul released a spellchecker a while ago, not sure if that would help (and it may be phonetic) but a search for variations on spell check might find it.

[netmaestro]

Searching it quickly is no problem as it is sorted and I can use the binary search technique. For a list of this size a search would be almost instantaneous given that the data is in memory and one million items can be searched with a maximum of 20 reads. I just need to be able to read the file.

[Dare2]

Okay. I am probably missing the point. But here goes:

To load:

Code: Select all

memSize=FileSize("myfile")+2
memFile=allocateMem(memSize)
tempHandle=OpenFile(#PB_Any,"myfile")
ReadData(memFile+1)
CloseFile(tempHandle)
PokeB(memFile,0)
PokeB(memFile+memSize,0)

Then the only issue is to make sure your binary search gets the full word? (I am assuming the file can be PeekS-ed). Perhaps a procedure like this (but you'll do it better, I'm sure)

Code: Select all

Procedure.s readMemoryString(offset.l)
  k=offset+memFile
  While PeekB(k)<>0
    k-1
  Wend
  k+1
  ProcedureReturn=PeekS(k)
EndProcedure

Where offset is your current binary search value.

Was that what you were looking for?

BTW, the above is typed directly into this post and not tested, just a concept.

Edit: Changed the "offset" to "k" in a couple of places. Also, as it is binaryIncluded, no need for the load. If using something like the above just make sure a binary zero is before the first word and at the end of the dictionary

[netmaestro]

Thanks Dare2, you gave me a push in the right direction. I managed to get a dll built that works nicely. I started with the idea that the data has to be included in the dll file and searchable quickly. So I figured that if all the dictionary words were uppercase, sorted and all 15 characters in length, it should be doable with a binary search. I took out all the newlines from the text file and replaced them with binary 0's to delimit the strings. It works and an average search takes less than one millisecond, which is fast enough for my purposes. The dll returns a float because the program calling it is made in Gamemaker and that program requires floats to be compatible with its REAL type. Here's what I have:

Code: Select all

ProcedureDLL.f CheckWord(wordtofind.s) 
  offset.l
  wordtofind = LSet(UCase(wordtofind),15)
  wordchecked.s = ""
  found.f = #False
  topoflist.l = 171326 ;number of words in list minus one
  lo = 0
  hi = topoflist
  While (hi-lo) > 1
    offset = lo+Int((hi-lo)/2)
    wordchecked=PeekS(?lex+(offset*16))
    If wordtofind=wordchecked
      hi=lo
      found = #True
    Else
      If wordtofind < wordchecked
         hi = offset
      Else
         lo = offset
      EndIf
    EndIf
  Wend
  If found=0 ;check the word above and below in case we missed by one
    If offset > 0
      If PeekS(?lex+((offset-1)*16)) = wordtofind
        found=#True
      EndIf
    EndIf
    If offset < topoflist
      If PeekS(?lex+((offset+1)*16)) = wordtofind 
        found=#True
      EndIf
    EndIf
  EndIf
  ProcedureReturn found

  DataSection 
    lex: 
    IncludeBinary "d:\books\lexicon.bin" 
  EndDataSection 
EndProcedure

The search technique is a bit rough as I didn't put in the effort to make it perfect. It certainly could be optimized but it's lightning fast and it doesn't make any mistakes.

Incidentally the wordlist is an officially authorized dictionary for Scrabble tournaments, containing the TWL98 word list and the 3235 recent OSPD4 additions from October 2005. It would be more than suitable as a spell checker or validator for word games. Its only drawback is that it weighs in at 2.6 megabytes. But what the heck, you can't have a 170,000 word dictionary in a couple of k.

[Truth_Seeker]

Nice code, I only see one problem. The file you are including will only work on your computer or a computer with that directory. Not everyone has a D drive.

[netmaestro]

Nice code, I only see one problem. The file you are including will only work on your computer or a computer with that directory. Not everyone has a D drive.
_________________
Thanks,
Truth Seeker

No, it will only compile on that computer and drive. Once built, the data is all inside the dll and fully portable. The .bin file doesn't have to be distributed at all.

[Truth_Seeker]

No, it will only compile on that computer and drive. Once built, the data is all inside the dll and fully portable.

Never mind, your right. Not sure what I was thinking

[Dare2]

Hi netmaestro,

Pretty nifty.

Just out of curiosity, what is the app? Crossword puzzle? Or is this something you've originated?

Also, dictionary sounds neat. Going to google for it now. I have dozens of dictionaries and word list files (from some scrabble site) but not the official scrabble dictionary.

[netmaestro]

It is for an online Scrabble program I wrote last year called WordConnect. I wrote it in Gamemaker and it has since been downloaded several thousand times from my site. I never did do a proper job of the dictionary for it, I just split the TWL98 text file into 8 parts and did a sequential search of the appropriate file from disk based on the first letter of the word to be checked. It worked fine but it was a piece of crap from an engineering standpoint. It was the only weakness in an otherwise superb (that's not from me - that's from my users) program. So when they released the October 2005 update I figured it was time to do it right. Btw I upx'd the dll and it went down to less than 900k with no performance hit. If you want to check WordConnect out it is on my site:

http://www.networkmaestro.com and hit the WordConnect button. Cheers and thanks for your help.

[okasvi]

hmm...you do realize that even tho it is upx'ed it will unpack itself into memory and around 2MB in memory for just dictionary seems to be bit of a waste

maybe you could use something like Xombie uses in his "Very Simple Binary Database" viewtopic.php?t=17059

but modified to be something like this:
BYTEword1BYTEword2BYTEword3... and BYTE would be the lenght of next word and word* would be any word im sure that with that method you could trim off alot of the size, but not having stringlenght of certain size does slow searching a little...

[netmaestro]

No, not by today's standards. 2mb out of 256 is nothing. It's not like it's going to have to page. Making a search the way you are talking about is certainly possible but to maintain reliability and not take too much of a speed hit would be a lot of work and intensive testing. I wrote what I have in under an hour and I know it's going to work. On to something else.

[GedB]

netmaestro,

After posting this a better method struck me. Please see the next post.

Funnilly enough I'm using your TW98 library for my own wordgame. Thanks

The megabyte threshold can have a strong impact when it comes to download decisions. I try to keep everything below a meg, because anything mor and I know that I would think twice before downloading.

Anyway, my solution uses the list of words with no space or nulls between them. Something like this (only all in upper case):

Code: Select all

                   1111111111222
Offset : 01234567890123456789012
Words:   CamelCatDogElephantFish

I then have an index that points to the start of each word. The length of any word can be found by looking at the start of the next word.

Code: Select all

0 5 8 11 19

Finally, both list and index are packed with maximum compression.

Here's the code for producing the packed binaries:

Code: Select all

;- Prepare Constants

Enumeration
  #File_Txt_TWL98
  #File_Bin_WordList
  #File_Bin_WordIndex
EndEnumeration

#Path_Folder = "C:\Documents And Settings\GByrne\Desktop\learning\wordlist\"
#Path_TWL98 = #Path_Folder + "Twl98.txt"
#Path_Bin_WordList = #Path_Folder + "WordList.bin"
#Path_Bin_WordIndex = #Path_Folder + "WordIndex.bin"

;- Read in the TWL98 Word List

If ReadFile(#File_Txt_TWL98,#Path_TWL98) = 0 
  MessageRequester("Information","Couldn't open the TWL98 file!")
  End
EndIf

TWL98_Size = Lof()

;- Read the Word list into memory and create an index

*WordIndex = AllocateMemory(TWL98_Size)
*WordList = AllocateMemory(TWL98_Size)

Debug TWL98_Size

WordOffSet = 0
IndexOffSet = 0
Length = 0
Word.s = ""

While Eof(#File_Txt_TWL98) = 0  
  
  Word = ReadString()
  Length = Len(Word)
  
  ;Keep 4 byte boundary for speed.  This could
  ;be packed tighter.
  ;eg. by using a byte For the lenth
  PokeL(*WordIndex + IndexOffset, WordOffset)
  IndexOffset + 4

  ;Use CopyMemory rather than PeekS to avoid 0s
  CopyMemory(@Word, *WordList + WordOffset, length)
  WordOffset + Length
  
  
  UseFile(#File_Txt_TWL98)
Wend

Debug IndexOffset + WordOffset

CloseFile(#File_Txt_TWL98) 

;- Pack and save the word list

*PackedList = AllocateMemory(WordOffset)
PackedListLength = PackMemory(*WordList, *PackedList, WordOffset, 9)

If OpenFile(#File_Bin_WordList, #Path_Bin_WordList) = 0
  MessageRequester("Information","Couldn't open the Binary Wordlist file!")
  End
EndIf
WriteLong(WordOffset)
WriteData(*PackedList, PackedListLength)
CloseFile(#File_Bin_WordList)

FreeMemory(*WordList)
FreeMemory(*PackedList)

;Pack and save the word index
;

*PackedIndex = AllocateMemory(IndexOffset)
PackedIndexLength = PackMemory(*WordIndex, *PackedIndex, IndexOffset, 9)

If OpenFile(#File_Bin_WordIndex, #Path_Bin_WordIndex) = 0
  MessageRequester("Information","Couldn't open the Binary WordIndex file!")
  End
EndIf

WriteLong(IndexOffset)
WriteData(*PackedIndex, PackedIndexLength)
CloseFile(#File_Bin_WordIndex)

FreeMemory(*WordIndex)

Then I BinaryInclude these two files and unpack them at run time.

Code: Select all

;-Helper functions

;The included binary files have a long showing the size of the expanded
;buffer, followed by the packed buffer.
;These procedure obtains the buffersize, allocates the necessary memory,
;expands the packed buffer and returns the pointer to the unpacked data.
Procedure Unpack(*Source)
  BufferSize = PeekL(*source)
  *buffer = AllocateMemory(BufferSize)
  If UnpackMemory(*Source + 4, *buffer) = 0
    ProcedureReturn 0
  Else
    ProcedureReturn *buffer
  EndIf
EndProcedure

;These are convenience functions so that the
;code reads easier.
Procedure WordIndexLength()
  ProcedureReturn PeekL(?WordIndex)
EndProcedure

Procedure WordIndex()
  ProcedureReturn Unpack(?WordIndex)
EndProcedure

Procedure WordListLength()
  ProcedureReturn PeekL(?WordList)
EndProcedure

Procedure WordList()
  ProcedureReturn Unpack(?WordList)
EndProcedure

Procedure WordCount()
  Static Count
  If count = 0 
    count = (WordIndexLength() / 4) - 2 ;WordIndex is 0 based and includes the end address
  EndIf
  
  ProcedureReturn Count
EndProcedure

;Rather than dealing with the buffer direct I view it as an
;indexed lists of words.  Given an Index the word is returned, 
;or an empty string if the index is out of bounds.
Procedure.s Word(Index)
  ;Index is 0 based
  
  Static WordCount
  Static WordIndexLength
  Static *WordIndex
  Static WordListLength
  Static *WordList
   
  ;Ensure the index is within bounds
  If index < 0
    ProcedureReturn ""
  EndIf
  
  ;Initialise the Static variables if necessary.
  If WordCount = 0
    WordCount = WordCount()
  EndIf
    
  If index > WordCount
    ProcedureReturn ""
  EndIf
  
  If WordIndexLength = 0
    WordIndexLength = WordIndexLength()
  EndIf
  If *WordIndex = 0 
    *WordIndex = WordIndex()
  EndIf
  If WordListLength = 0
    WordListLength = WordListLength()
  EndIf
  If *WordList = 0 
    *WordList = WordList()
  EndIf  
  
  ;Find the position of the word within the buffer
  WordOffset = PeekL(*WordIndex + ( Index * 4 ))
  
  ;Find the length by checking the start of the next word.
  WordLength = PeekL(*WordIndex + ( (Index + 1) * 4 ) ) - WordOffset
  
  ;Return the word as a string.  
  ProcedureReturn PeekS(*WordList + WordOffset, WordLength)

EndProcedure

; Check that a given word exists
Procedure.f WordExists(WordToFind.s)
  ;Ensure we don't have an empty string
  If WordToFind = ""
    ProcedureReturn #False
  EndIf
  
  
  ;Perform a binary search through the word list.
  lo = 0
  hi = WordCount()

  While (hi-lo) > 1
    current = lo + (hi-lo)/2
    wordchecked.s =Word(current)
    If wordtofind=wordchecked
      ProcedureReturn #True
    Else
      If wordtofind < wordchecked
         hi = current
      Else
         lo = current
      EndIf
    EndIf
  Wend

  ;The binary search may be off by one
  If Word(current-1) = wordtofind
    ProcedureReturn #True
  EndIf
  If Word(current+1) = wordtofind
    ProcedureReturn #True
  EndIf
  
  ProcedureReturn #False
  
EndProcedure

;Do a quick test
Debug WordExists("ABALONE")
Debug WordExists("ABALONEE")
Debug WordExists("ABALONES")

DataSection
;Include our packed word list and index.

WordIndex:
IncludeBinary("WordIndex.bin")

WordList:
IncludeBinary("WordList.bin")

EndDataSection

The example here compiles to 829kb when using the 1.74mb TWL98 file from your website.

If you're interested, feel free to use and adapt my code any way you see fit.

[GedB]

I don't know why I didn't see this before.

If you puts 0's into the word list, and update the offsets into the index into true pointers by adding the buffers base then you can access it all through a structure.

Here's the simplified code. If you want to use UPX rather than packing then it can be even simpler still.

For creating the binaries:

Code: Select all

;- Prepare Constants

Enumeration
  #File_Txt_TWL98
  #File_Bin_WordList
  #File_Bin_WordIndex
EndEnumeration

#Path_Folder = "C:\Documents And Settings\GByrne\Desktop\learning\pb\wordlist\"
#Path_TWL98 = #Path_Folder + "Twl98.txt"
#Path_Bin_WordList = #Path_Folder + "WordList.bin"
#Path_Bin_WordIndex = #Path_Folder + "WordIndex.bin"

;- Read in the TWL98 Word List

If ReadFile(#File_Txt_TWL98,#Path_TWL98) = 0 
  MessageRequester("Information","Couldn't open the TWL98 file!")
  End
EndIf

TWL98_Size = Lof()

;- Read the Word list into memory and create an index

*WordIndex = AllocateMemory(TWL98_Size)
*WordList = AllocateMemory(TWL98_Size)

WordOffSet = 0
IndexOffSet = 0
WordCount = 0
Length = 0
Word.s = ""

While Eof(#File_Txt_TWL98) = 0  
  
  Word = ReadString()
  
  WordCount + 1
  
  ;Keep 4 byte boundary for speed.  This could
  ;be packed tighter.
  ;eg. by using a byte For the lenth
  PokeL(*WordIndex + IndexOffset, WordOffset)
  IndexOffset + 4

  
  PokeS(*WordList + WordOffset, Word)
  WordOffset + Len(Word) + 1 ; Allow one for Null marker
  
  
  UseFile(#File_Txt_TWL98)
Wend

CloseFile(#File_Txt_TWL98) 

;- The Debug output (constant declaration can be pasted into code)
Debug "#Word_Index_Size = " + Str(IndexOffset)
Debug "#Word_List_Size = " + Str(WordOffset)
Debug "#Word_Count = " + Str(WordCount)
End
;- Pack and save the word list

*PackedList = AllocateMemory(WordOffset)
PackedListLength = PackMemory(*WordList, *PackedList, WordOffset, 9)

If OpenFile(#File_Bin_WordList, #Path_Bin_WordList) = 0
  MessageRequester("Information","Couldn't open the Binary Wordlist file!")
  End
EndIf

WriteData(*PackedList, PackedListLength)
CloseFile(#File_Bin_WordList)

FreeMemory(*WordList)
FreeMemory(*PackedList)

;Pack and save the word index
;

*PackedIndex = AllocateMemory(IndexOffset)
PackedIndexLength = PackMemory(*WordIndex, *PackedIndex, IndexOffset, 9)

If OpenFile(#File_Bin_WordIndex, #Path_Bin_WordIndex) = 0
  MessageRequester("Information","Couldn't open the Binary WordIndex file!")
  End
EndIf

WriteData(*PackedIndex, PackedIndexLength)
CloseFile(#File_Bin_WordIndex)

FreeMemory(*WordIndex)

For using the binaries:

Code: Select all

;-Constants
#Word_Index_Size = 672372
#Word_List_Size = 1660544
#Word_Count = 168093

;-Helper functions

;The included binary files have a long showing the size of the expanded
;buffer, followed by the packed buffer.
;These procedure obtains the buffersize, allocates the necessary memory,
;expands the packed buffer and returns the pointer to the unpacked data.
Procedure Unpack(*Source, BufferSize)
  *buffer = AllocateMemory(BufferSize)
  If UnpackMemory(*Source, *buffer) = 0
    ProcedureReturn 0
  Else
    ProcedureReturn *buffer
  EndIf
EndProcedure

;Unpacks the included binaries and then returns a pointer to the
;word index, which can then be read using the WordList structure
Structure WordList
  List.s[#Word_Count]
EndStructure


Procedure.l WordArray()
  
  Static *WordIndex
  Static *WordList
   
  If *WordIndex = 0 
    *WordIndex = Unpack(?WordIndex, #Word_Index_Size)
  EndIf
  If *WordList = 0 
    *WordList = unpack(?WordList, #Word_List_Size)
  EndIf  
  
  ;Update all of the offsets to include the base so that
  ;they become true pointers
  For i = *WordIndex To *WordIndex + #Word_Index_Size Step 4
    Offset = PeekL(i)
    PokeL(i, *WordList + Offset)
  Next i
  
  ;Return a pointer to the index
  ProcedureReturn *WordIndex

EndProcedure

;- Check that a given word exists
Procedure.f WordExists(WordToFind.s)
  Static *Word.WordList
  If *Word = 0
    *Word = WordArray()
  EndIf
  
  ;Ensure we don't have an empty string
  If WordToFind = ""
    ProcedureReturn #False
  EndIf
  
  ;Perform a binary search through the word list.
  lo = 0
  hi = #Word_Count

  While (hi-lo) > 1
    current = lo + (hi-lo)/2
    wordchecked.s = *Word\List[current]

    If wordtofind=wordchecked
      ProcedureReturn #True
    Else
      If wordtofind < wordchecked
         hi = current
      Else
         lo = current
      EndIf
    EndIf
  Wend

  ;The binary search may be off by one
  If current > 0 And *Word\List[current-1] = wordtofind
    ProcedureReturn #True
  EndIf
  If current < #Word_Count And *Word\List[current+1] = wordtofind
    ProcedureReturn #True
  EndIf
  
  ProcedureReturn #False
  
EndProcedure


;Do a quick test
Debug WordExists("ABALONE")
Debug WordExists("ABALONEE")
Debug WordExists("ABALONES")

DataSection
;Include our packed word list and index.

WordIndex:
IncludeBinary("WordIndex.bin")

WordList:
IncludeBinary("WordList.bin")

EndDataSection

You could build the index dynamically if you wanted, but that would slow down startup.

[GedB]

And finally, the simplest solution.

This version just reads the text file in exactly as it is, no preparation required.

At initialisation the CRLFs are replaced with 0s and an index created.

The index is then used through a structure.

The only prerequisite is that you need to know the word count and enter it into the #word_count constant.

This is why I love PB.

Code: Select all

;- Constants
#word_count = 168091
#CRLF = $0A0D

;- Sructures 
Structure Word_Array
  List.s[#word_count+1]
EndStructure

;- Prepare WordArray

;  Loop through the included text file
;  replacing the CRLF with chr(0) and 
;  building an index
;  List[0] is empty to make this array 1 based
Procedure WordArray()
  *Word.Word_Array = AllocateMemory((#word_count+1)*4)
  word_pointer = *Word + 4
  last_word = ?word_list_start
  For i = ?word_list_start To ?word_list_end 
    char.w = PeekW(i)
    If char = #CRLF
      PokeW(i, 0)
      PokeL(word_pointer, last_word)
      word_pointer + 4
      last_word = i + 2
    EndIf
  Next i
  ProcedureReturn *Word
EndProcedure

;- Check that a given word exists
Procedure.f WordExists(WordToFind.s)
  Static *Word.Word_Array
  If *Word = 0
    *Word = WordArray()
  EndIf
 
  ;Ensure we don't have an empty string
  If WordToFind = ""
    ProcedureReturn #False
  EndIf
 
  ;Perform a binary search through the word list.
  lo = 1
  hi = #Word_Count

  While (hi-lo) > 1
    current = lo + (hi-lo)/2
    wordchecked.s = *Word\List[current]

    If wordtofind=wordchecked
      ProcedureReturn #True
    Else
      If wordtofind < wordchecked
         hi = current
      Else
         lo = current
      EndIf
    EndIf
  Wend

  ;The binary search may be off by one
  If current > 1 And *Word\List[current-1] = wordtofind
    ProcedureReturn #True
  EndIf
  If current < #Word_Count And *Word\List[current+1] = wordtofind
    ProcedureReturn #True
  EndIf
 
  ProcedureReturn #False
 
EndProcedure

;Do a quick test
Debug WordExists("ABALONE")
Debug WordExists("ABALONEE")
Debug WordExists("ABALONES")

DataSection
word_list_start:
IncludeBinary("twl98.txt")
word_list_end:

EndDataSection