Create Dictionary in Javascript / PHP

Question

I'm trying to create a dictionary from a .txt file in the shape of a tree. On every line of the text file there's a word, I extract all those words in an array.

Now regarding the tree, Each node contains a letter, if it's the last letter of a word, it contains a definition, and each node have an array Children that contains letters from all others words starting the same way.

So I have nodes defined this way:

function Node(letter,definition,children) {
   this.letter = letter,
   this.definition = "",
   this.children = [] 
};

I have an array Dictionary that will contain all the nodes. Every Node will be organized (so that we know 'a' is in Dictionary[0] and 'b' in Dictionary[1] and so on).

I defined some functions to help build the dictionary:

• check if Dictionary contains the first letter of the word we have (c is the character, dictio is the dictionary array and ascii is the ascii-97 value of the character)

  function checkChar(c,dictio,ascii){
      if(dictio[ascii].letter == c ){
          return true;
      }
      return false;
  };
  

  • create a node with the given character

    function createChar(c){
    
        var noeud = {
            letter: c,
            def: '',
            children: [] 
        };
    
        return noeud;
    };
    

• Add the character to the dictionary

  function addChar(c,dictio,ascii){ dictio.children[ascii] = createChar(c); };

• And I'm having trouble on the biggest function: the main on that adds the word and calls all of these small functions I've written. Which I'm having trouble making.

I don't even know if what I'm doing is right or wrong, if anyone could point me to the right direction or suggest a method in javascript or php to do dictionary from a TXT file that would be great.

Answer 1

Ok...

so this is an example of txt file containing words

//words.txt
hello
world
foo
bar

word_dictionary.php for parsing txt file and has method for checking if a word exists in tree/dictionary

<?php 
//word_dictionary.php
class Node{
    private $letter;
    private $definition = '';
    private $children = array();

    function __construct($letter){
        $this->letter = $letter;
    }

    function hasChild($letter){
        return array_key_exists($letter,$this->children);
    }

    function addChild($letter){
        $this->children[$letter] = new Node($letter);
        return $this->children[$letter];
    }

    function getChild($letter){
        return $this->children[$letter];
    }

    function setDefinition($definition){
        $this->definition = $definition;
    }

    function getDefinition(){
        return $this->definition;
    }

    function hasDefinition(){
        return (bool)$this->definition;
    }
}

// method for getting a word definition from tree/dictionary.
// if word exists return definition, else return false
function getDefinition($word,$tree){
    $node = $tree;
    $length = strlen($word);
    foreach(str_split($word) as $index => $letter){
        if($node->hasChild($letter)){
            $node = $node->getChild($letter);
        }
        else{   // word not exists
            return false;
        }
        if(($index+1) == $length){      // means last letter in word
            return ($node->hasDefinition()) ? $node->getDefinition() : false;
        }
    }   
}

// Start build your tree/dictionary. This part is execute ONCE only for building tree.
$anchor = new Node('');
$handle = fopen('words.txt','r');
while(($word = fgets($handle))){
    $word = rtrim($word);
    $length = strlen($word);
    $node = $anchor; 
    foreach(str_split($word) as $index => $letter){

        if($node->hasChild($letter)){
            $node = $node->getChild($letter);
        }
        else{
            $node = $node->addChild($letter);
        }

        if(($index+1) == $length ){
            //print 'definition for word: '.$word."\n";
            $node->setDefinition('definition for world: '.$word);   
        }
    }
} 

//use this function when a user type a word that you want to check if exists and return the definition to user. this flow should be in AJAX request from client 
print getDefinition('bar',$anchor)."\n";

hope it help a bit ;)

Answer 2

first of all, you're asking if you are going in the right direction. Well, i think you are. This may not be the best implementation of the year but still all the things you said are coherent with each other and it seems pretty solid.

I don't think giving you a direct solution to your question would be didactic since you're working with trees and it seems you don't have much experience with them.

But i can give you some hint and references. A very convenient way to implement your "biggest function :)" would be to use a recursive function which would call itself on each children.

I suggest you take a look a this wikipedia article. It shows example of trees that look a bit like yours and implement a full search algorithm that you could adapt to your needs without too much problem.

Hope the english wasn't that bad, and that it will help you