`
m2000hsf
  • 浏览: 99146 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

大并发搜索下关键词前缀匹配值得考虑的一种数据结构---Trie

 
阅读更多
如果要实现一个能支撑大数据量并发搜索的引擎的关键词匹配,而是需要选择用一种紧凑高效的数据结构来实现,譬如说Trie。下面介绍一下Trie..
Trie,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。

散列是一种常见的高效查找方法,它根据数组下标查询,所以速度快。首先根据词表构造散列表,具体来说就是用给定的哈希函数构造词典到数组下标的映射,如果存在冲突,则根据选择的冲突处理方法解决地址冲突。然后可以在哈希表的基础上执行哈希查找。

冲突导致散列性能降低。不存在冲突的散列表叫做完美散列(perfect hash)。整词散列不适合分词的最长匹配查找方式。

数字搜索树采用了逐字散列的方法,可以看成是一种逐字的完美散列。一个数字搜索Trie树(retrieve树)的一个节点只保留一个字符。如果一个单词比一个字符长,则包含第一个字符的节点有指针指向下一个字符的节点,以此类推。这样组成一个层次结构的树,树的第一层包括所有单词的第一个字符,树的第二层包括所有单词的第二个字符,以此类推,数字搜索树的最大高度是词典中最长单词的长度。例如,如下单词序列组成的词典(as  at  be  by  he  in  is  it  of  on  or  to)会生成如图4-4所示的数字搜索树:

数字搜索树的结构独立于生成数时单词进入的顺序。这里,Trie树的高度是2。因为树的高度很小,在数字搜索Trie树中搜索一个单词的速度很快。但是,这是以内存消耗为代价的,树中的每一个节点都需要很多内存。假设每个词都是由26个小写英文字母中的一个组成的,这个节点中会有26个指针。所以不太可能直接用这样的数字搜索树来存储中文这样的大字符集。

它有3个基本性质:
    根节点不包含字符,除根节点外每一个节点都只包含一个字符。
    从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
    每个节点的所有子节点包含的字符都不相同。
这是一个Trie结构的例子: Trie example.svg


在这个Trie结构中,保存了A、to、tea、ted、ten、i、in、inn这8个字符串,仅占用8个字节(不包括指针占用的空间)。

Trie树在实现上有一个树类(SearchTrie)和一个节点类(TrieNode)。SearchTrie的主要方法有两个:
增加单词到搜索树,方法原型是:addWord(String word)。
从文本的指定位置开始匹配单词,方法原型是:matchLong(String text,int offset)。

给定一个固定电话号码,找出这个电话号码对应的区域。固定电话号码都是以0开始的多位数字,可以通过给定电话号码的前缀找出对应的地区,例如:

0995:新疆:托克逊县  
    0856:贵州:铜仁  
    0996:新疆:焉耆回族自治县


可以使用数字搜索树算法快速查找电话号码前缀。例如:0 3 7 1 这个区号有四个节点对应,也就是说有4个TrieNode对象。第一个对象中的splitChar属性是0;第二个对象中的splitChar属性是3;第三个对象中的splitChar属性是7;第四个对象中的splitChar属性是1。每个TrieNode对象有10个孩子节点,分别对应孩子节点的splitChar为0到9。
Trie树的节点类定义如下:
   
public static final class TrieNode {  
            protected TrieNode[] children; //孩子节点  
            protected char splitChar;   //分隔字符  
            protected String area;   //电话所属地区信息  
     
            /**  
             * 构造方法  
             *  
             * @param splitchar分隔字符  
             */  
            protected TrieNode(char splitchar) {  
                children = new TrieNode[10];  
                area = null;  
                this.splitChar = splitchar;  
            }  
    }  

加载词,形成数字搜索树的方法如下:

    private void addWord(String string, TSTNode root, String area) {  
            TSTNode tstNode = root;  
            for (int i = 1; i < string.length(); i++) {  
                char c0 = string.charAt(i);  
                int ind = Integer.parseInt(string.substring(i, i + 1));  
                TSTNode tmpNode = tstNode.children[ind];  
                if (null == tmpNode) {  
                    tmpNode = new TSTNode(c0);  
                }  
                if (i == string.length() - 1) {  
                    tmpNode.area = area;  
                }  
                tstNode.children[ind] = tmpNode;  
                tstNode = tmpNode;  
            }  
    }
 

查询的过程对于查询词来说,从前往后一个字符一个字符的匹配。对于Trie树来说,是从根节点往下匹配的过程。从给定电话号码搜索前缀的方法如下所示:
   
public String search(String tel) {  
        TrieNode tstNode = root;  
        for (int i = 1; i < tel.length(); i++) 
    {//从前往后一个字符一个字符的匹配  
                tstNodetstNode = tstNode.children[(tel.charAt(i)-'0')];  
            if (null != tstNode.area) {  
                return tstNode.area;  
            }  
        }  
        return null;//没找到  
    }
 

考虑把Trie树改成通用的结构,使用散列表存储孩子节点,并使用范型定义值类型。
  
 public class TrieNode<T> {  
        private Character splitChar;  //分隔字符  
        private T nodeValue;  //值信息  
        private Map<Character, TrieNode<T>> children =   
                                new HashMap
    <Character, TrieNode<T>>();  
                            //孩子节点  
    }
 

Java 实现

/**
 * Description: This program implements a trie that allows to search words. It 
 *          reads words from a file specified by the user in the command line 
 *          and constructs the dictionary. It allows user to find, print, add, 
 *          and delete words from the trie. It folds all inpput into lower-case 
 *          before storing them or looking them up. It also ignores characters 
 *          that are not letters and only stores words that are three letters
 *          long. A reference pointer is used, when finding a word, the reference 
 *          pointer will point to this word, when printing it will point to the
 *          last printed word, and when deleting it will be reset to the trie root.
 * 
 *          This class implements a dictionary tree in a structure called trie. 
 *          We use a representation called "Leftmost-Child-Right-Sibling" 
 *          representation. A node points to a list of its children and it points 
 *          to the leftmost child in the list, and each child in the list points 
 *          to the sibling to the right of it. We add one extra node at the end 
 *          of the list to implement a pointer back to the parent, using the child 
 *          pointer in that extra node. The root does not represent any letter, and 
 *          the last sibling on each list (that points to the parent) has a right 
 *          sibling pointer set to null.      
 *
 *          There is a pointer to the current position in the trie, this position 
 *          is updated when we search a word to point to the start of the found 
 *          word, when printing it points to the starting position of last printed 
 *          word, and when deleting it resets position reference to the root. Finding 
 *          and adding work in the same way, checking first if child node match letter 
 *          if not then checking with siblings, until a match is found. Printing starts 
 *          from the starting node position of the word, it goes to the end of the sibling 
 *          list and then up to the parent node, gets its letter and continues until it 
 *          get to the root. Deleting starts also from the node starting position of the 
 *          word and continuous up the tree in the same as printing, but checking on its 
 *          way if the nodes are still useful, if not it removes reference to these nodes. 
 *          The basic structure of the trie is a node that contains a specific letter of a 
 *          word, a child pointer, a sibling pointer and a boolean vallue indicating if 
 *          this is the starting position of a word. The construction of the trie is done 
 *          by reading the input file one line at a time and using the add word method. 
 *
 * Input:   It receives as input in the command line the name of the filename to 
 *          be used as input in constructing the trie.
 *          Later it receives input telling what operation to perform: add, delete 
 *          or find a word, or print n number of words
 * Output:  It prints out wether the operation requested by the user was succesful 
 *          or not, and the output requested by each command. 
 *          
 * Status:  This class works according to program specifications       
 */

import java.io.*;               // For console input 

public class Trie
{
    public Node root;          // Trie root
    public Node current;       // Current Position Inside the Trie
    
    /** Array of letters that are used in comparison operations in order to 
     *  know which letter is currently being stored into the trie */
    private String[] letters = {"a", "b", "c", "d", "e", "f", "g", "h", "i", 
                                "j", "k", "l", "m", "n", "o", "p", "q", "r", 
                                "s", "t", "u", "v", "w", "x", "y", "z"};
                                
    /** Stores the ocurrence of each letter read into the trie, the counter 
     * stored at each index corresponds to the letter stored at the same index
     * in array letters */
    private double[] letterCount = new double[26];
    
    /** Stores the percentage of ocurrence of each letter in the trie, the
     * precentage stored at each  index corresponds to the letter stored at the
     * same index in array letters */
    private double[] percentageOfLetter = new double[26];
    
    // Total number of letters read into the trie
    private double totalLetterCount;
    
    // Numbers used in calculating a random number to find a random letter
    private final double max = 100.0;
    private final double min = 0.0;    
    
    /**
     * Declares an empty trie
     */
    public Trie()
    {
        Node root = new Node();
    }

    /**
     * Build the dictionary trie reading the input from a given filename
     * @param   An array of strings with the command line arguments
     * @return  None
     */
    public Trie(String[] commandLine) throws IOException { 
        
        root = new Node();              // Declare a new trie
        BufferedReader reader;          // To read from a file
        String input;                   // Store line of input
        
        // Check if filename was declared and if it exists
        checkIfValidFilename( commandLine );  
        
        // Declare in which file the input is in
        reader = new BufferedReader( new FileReader ( commandLine[0] ) );    
        
        // Declare in which file the input is in
        //reader = new BufferedReader( new FileReader ( "words" ) );    

        // Read each line of the input file
        while ( (input = reader.readLine() ) != null) {  
            
            // Add word to trie
            addWord(input);                    
        }
        
        // current position in trie is the root
        current = root;
        
        // Calculate percentage of ocurrence of letters 
        calculatePercentages();
    }
    
    /**
     *  Description: Node
     *               This class implement a node structure which is used as the
     *               structural components of the trie
     */
    public class Node{
        private String letter;  // Letter hold in the node    
        boolean isAWord;        // Indicates wether this node represents starting positionof a word
        private Node next;      // Leftmost child pointer
        private Node sibling;   // Right sibling pointer
    
        /**
         * Creates a new node
         * @param   None
         * @return  None
         */
        Node () {                    
            letter = null; 
            isAWord = false;
            next = sibling = null;
        }

        /**
         * Creates a new node with given letter and boolean value
         * @param   A string for the letter hold in node
         *          A boolean value to check if this the start of a word
         * @return  None
         */        
        Node (String s) {                    
            letter = s;
            isAWord = false;
            next = sibling = null;
        }       
    }
    
    // Check if the given letter is in the next level of the trie from the given node pointer
    // Returns boolean if it finds it, else returns null
    public Node findLetter(Node crtPosition, String letter) {        
        Node pointer = crtPosition;                // Initialize pointer for position refernce in trie
                
        // Word is not in tree if still looking for word letters and there aren't any more
        if (pointer.next == null) { 
            return null;
        }
        else {  // There is a child from the current node
            
            // Check if next node contains the current letter we're looking for
            if ( pointer.next.letter.equals(letter) ) {   
                pointer = pointer.next;                 // go to next child
            }
            else {  // Check if a sibling contains the same letter
                pointer = pointer.next;                 // go to start of node sibling list
                  
                // Loop until a node with the same letter is found or sibling list ends  
                while ( pointer.sibling.sibling != null && !pointer.sibling.letter.equals(letter) ) {
                    pointer = pointer.sibling;
                }
                
                // If no sibling with same letter is found, word isn't in trie
                if ( pointer.sibling.sibling == null ) {
                    return null;        // String is not in tree
                }
                else {  // A sibling has the letter we're looking for, continue
                    pointer = pointer.sibling;  // One sibling has same letter
                }
           }
        }
        return pointer;
    }
    
    
    /**
     * Find a given word in the given trie 
     * @param   A string to look up in the trie
     *          The root of the trie in where to look up the word
     * @return  A pointer to the node with the starting position (letter) of the word found
     *          If word is not found, it returns a null pointer
     */
    public Node findStr(String word) {        
        Node pointer = root;                // Initialize pointer for position refernce in trie
        String input = word;                // Word to look up
        
        // Start a while lopp searching the chars of the word in trie starting backwards
        while (input.length() >= 1) {
            
            // Get the last letter in the word
            String firstChar = input.substring( 0, 1 );
            input = input.substring( 1, input.length() );     // Update string minus last letter
        
            if ( !Character.isLetter(firstChar.charAt(0)) ) {    // If char is not a letter skip it
                continue;
            }
                
            // Word is not in tree if still looking for word letters and there aren't any more
            if (pointer.next == null) { 
                return null;
            }
            else {  // There is a child from the current node
                
                // Check if next node contains the current letter we're looking for
                if ( pointer.next.letter.equals(firstChar) ) {   
                    pointer = pointer.next;                 // go to next child
                }
                else {  // Check if a sibling contains the same letter
                    pointer = pointer.next;                 // go to start of node sibling list
                      
                    // Loop until a node with the same letter is found or sibling list ends  
                    while ( pointer.sibling.sibling != null && !pointer.sibling.letter.equals(firstChar) ) {
                        pointer = pointer.sibling;
                    }
                    
                    // If no sibling with same letter is found, word isn't in trie
                    if ( pointer.sibling.sibling == null ) {
                        return null;        // String is not in tree
                    }
                    else {  // A sibling has the letter we're looking for, continue
                        pointer = pointer.sibling;  // One sibling has same letter
                    }
               }
           }
        }
        // All letters from word match, check if current pointer reference is start of word
        if ( pointer.isAWord == true) {    
            current = pointer;
            return pointer;     // Return pointer to start of found word
        }
        else {  // Letters matched, but it not a word in the tree          
            return null;        // String is not in tree
        }
    }

    /**
     * Print n number of words starting from a given reference in the trie
     * @param   The root of the trie
     *          The current reference pointer in the trie
     *          The number of words to be printed
     * @return  A pointer reference to the last word printed
     */
    public Node printNextWords( int n) {
        Node pointer = current;
        
        if (root.next == null) {    // check if Dictinary has no words
            System.out.println(" Trie is Empty");
            return root;
        }
        System.out.println();
        
        // Start loop to print n number of words
        while ( n > 0) {
            
            // Check if we are at the end of the trie or there is no child
            if ( pointer.next == null || pointer.next == root) {
                
                if ( pointer.next == root) {    // We are at the end of the trie
                    System.out.println(">> End of Trie <<");              
                    pointer = root;             // Reset the position reference
                    break;                      // Stop printing words
                }
                else {  // Pointer has no child
                    pointer = pointer.sibling;      // Goto pointer sibling
                    
                    // If we are at the end of the list, back up to parent node next sibling
                    while ( pointer.sibling == null ) {
                        if ( pointer.next == root ) {   // We are at the end of the trie
                            break;                      // Stop printing words       
                        }
                        else {  // Back up to parent node next sibling, list in above level
                            pointer = pointer.next.sibling;
                        }
                    }
                    if ( pointer.isAWord == true) { // If pointer is start of word, prin it
                        printWord(pointer);
                        n--;                        // Decrement words to print counter
                    }
                }
            }
            else {  // Child of current reference pointer is not null
                pointer = pointer.next;
                if ( pointer.isAWord == true) {     // If pointer is start of word, prin it
                    printWord(pointer);
                    n--;                            // Decrement words to print counter
                }
            }   
        }
        current = pointer;
        return pointer;     // Pointer to last word printed
    }
        
    /**
     * Delete a given word from given trie
     * @param   String to be found and deleted
     *          The root from the given trie
     * @return  A pointer to the next closest parent from the current nodes deleted
     *          If word to be deleted is not found, returns a null pointer
     */
    public Node deleteWord(String lookUpWord) {
        Node pointer = findStr( lookUpWord);      // Check if word is in tree
        Node tempPointer = null;                        // Extra reference pointer
        
        if (pointer == null) {      // Word is not in tree
            return null;
        }
        else {      // Word is in trie, delete it            
            if ( pointer.next != null ) {            // Word starting position has children nodes
                pointer.isAWord = false;             // No longer represents a word
                return pointer;
            }
            else {                                  // Word starting position has no children nodes
                tempPointer = pointer;
                
                while (true) {  //  Loop until all parts of the word not used by others are deleted
                    
                    do {    // Go to the parent of the sibling list node of current pointer
                        tempPointer = tempPointer.sibling;
                    }   while ( tempPointer.sibling != null );          // Goto last sibling
                    tempPointer = tempPointer.next;                     // Goto parent
                    
                    // Check if our node is inmmediate child & has no children or siblings
                    if ( tempPointer.next == pointer && pointer.sibling.sibling == null) {       
                        tempPointer.next = null;        // Delete reference to child
                        
                        if ( tempPointer == root) { // We have arrived to root, no more to delete
                            break;
                        }
                        
                        // if parent is not the start of a word, it needs to be deleted
                        if ( tempPointer.isAWord == false ) {
                            pointer = tempPointer;      // Point now to the parent 
                            continue;
                        }
                        else {  // parent is a word, can not delete anymore nodes
                            break;
                        }
                    }
                    else {  // Current pointer has sibling nodes
                                                  
                        // check if child is pointer first in sibling list, 
                        if ( tempPointer.next == pointer ) { 
                            // update the child to be the pointer's sibling
                            tempPointer.next = tempPointer.next.sibling;
                            break;
                        }                                                
                        tempPointer = tempPointer.next;     // Pointer is not first sibling
                        
                        // Find node previous to our start of word node
                        while ( tempPointer.sibling != pointer ) {
                            tempPointer = tempPointer.sibling;
                        }
                        
                        // Update reference of previous node to pointer sibling
                        tempPointer.sibling = pointer.sibling;
                        break;
                    }
                }
            }
        }
        return tempPointer;
    }
            
    /**
     * Add a word to the trie
     * @param   The root of the trie
     *          The string to be added
     * @return  None
     */
    public Node addWord(String input) {
        Node pointer = root;  
	
	// Remove characters that are not letters
	input = removeNonLetterChars(input);
        
        // The words in this trie have to be at least 3 characters long
        if (input.length() < 3 ) {
            return pointer;
        }
        
        input = input.toLowerCase();        // Convert string to lower case
        
        while (input.length() >= 1) {            
            
            // Get the first letter of the word
            String firstChar = input.substring( 0, 1 );
            
            // Update string minus first letter
            input = input.substring( 1, input.length() ); 
                
            // If char is not a letter skip it    
            if ( !Character.isLetter(firstChar.charAt(0)) ) {    
                continue;
            }
            
            // Keep track of letters read into the trie
            countLetter(firstChar);
                          
            if (pointer.next == null) {     
                // No more child nodes, We need to add a new child
                Node newChild = new Node(firstChar);
                // Set child to be new node
                pointer.next = newChild;          
                    
                // Create the last sibling in list pointing to parent    
                Node lastSibling = new Node();    
                lastSibling.sibling = null;
                lastSibling.next = pointer;
                newChild.sibling = lastSibling;
                    
                pointer = newChild;              // Update pointer
            }
                
            else {  // There is still children nodes         
                if ( pointer.next.letter.equals(firstChar) ) { 
                    // node has same letter, go to next child
                    pointer = pointer.next;
                }                    
                else {  // Child has not the same letter we're looking for
                    pointer = pointer.next;
                                                
                    // Check if there's a sibling with same letter
                    while ( pointer.sibling.sibling != null && 
                            !pointer.sibling.letter.equals( firstChar ) ) {
                                
                        pointer = pointer.sibling;
                    }
                        
                    // Check if we got tothe last sibling, node matching letter was not found    
                    if (pointer.sibling.sibling == null) { 
                        
                        // Add new node at end of sibling list
                        Node newSibling = new Node(firstChar);        
                        newSibling.sibling = pointer.sibling;
                        pointer.sibling = newSibling;
                        pointer = newSibling;
                    }
                    else {  
                        //There is a node matching the letter we're looking for
                        // update pointer to this position
                        pointer = pointer.sibling;      
                    }
                }
            }
        }        
        if ( pointer == root ) {    // All characters in word were not a letter  
            return null;                 // No word will be added
        }        
        pointer.isAWord = true;       
        return pointer;
    }

    /**
     * Print a word that that starts at the given pointer reference
     * @param   A node referencce pointer
     * @return  None
     */
    public void printWord(Node pointer) {
        String word = "";       // Declaration of string to hold word to print
        
        do {
            word = pointer.letter + word;       // Store next character of word
            
            do {    // Go to the end of the sibling list
                pointer = pointer.sibling;
            }   while ( pointer.sibling != null );    
            
            pointer = pointer.next;             // Go to the parent of the node
                        
        }   while (pointer.sibling != null );   // Stop when we get to the root
        
        System.out.println(word);               // Print word
    }
    
    /** 
     * Get a random letter contained inside the trie based on how often it 
     * occurs in the trie
     * @ param  None
     * @ return A string containing a letter
     */
    public String getRandomLetter() {
        
        /** The method used to get arandom letter is based on the percentage of
         * how many times it was read into the trie. It gets a random number 
         * between 0.0 and 100.00, it adds the percentages of letters starting
         * from "a" to "z" until a number equal or bigger than the random 
         * number is found, then we take the letter where this occurred as the
         * random letter.
         */
        
        String randomString = null;
        double temp = 0.0;
        
        // Get a random number between 0.0 and 100.0
        double randomNumber = Math.floor (Math.random() * ( max - min + 1) ) + min;
        
        // Add the ocurrence percentages of each letter starting from "a" to "z"
        for (int i = 0; i < percentageOfLetter.length; i++) {
            
            // Store the percentage sum
            temp = percentageOfLetter[i] + temp;
            
            // Stop when the sum is equal or bigger than random number
            if ( temp >= randomNumber ) {
                randomString =  letters[i];
                break;
            }
        }
        
        // Return letter where the sum isequal or bigger than random number
        return randomString;
    }

    /** 
     * Count the number of times aeach letter is read in the trie
     * @ param  A string containing the letter to be counted
     * @ return None
     */
    public void countLetter(String letter) {
         String temp;                   // Temporary string holder
         
         // Compare letter to array containing alphabet letters
         for (int i = 0; i < letters.length; i++ ) {
            temp = letters[i];
            
            // If a match is found
            if ( temp.equals( letter ) ) {
                
                // Increase counter of that particular letter
                letterCount[i]++;
                
                // Increase counter of total letters read
                totalLetterCount++;
            }
         }
    }
    
    /** 
     * Calculate the percentage of ocurrance of all letters read into trie
     * @ param  None
     * @ return None
     */
    public void calculatePercentages() {
        
        // Valculate the percentage of ocurrence of each letter 
        for (int i = 0; i < percentageOfLetter.length; i++) {
            
            // Math formula: Percentage ox X = times X occurs * 100 / total
            percentageOfLetter[i] = (letterCount[i] * 100) / totalLetterCount;
        } 
    }
    
    /**
     * Checks if a file was specified by the user in the inputline to use as input to 
     * build the trie, and if it was declared, it checks it exists.
     * @param   A string array containing the arguments from the command line
     * @return  None
     */
    public static void checkIfValidFilename( String[] commandLine) throws IOException {
        int numberOfArgs = commandLine.length;      // Number of arguments in command line
        
        // Check if an input file was actually declared
        if ( numberOfArgs < 1 ) {
            System.out.println( " No Input File Declared." );
            System.out.println( " Ending Program . . . \n" );
            System.exit(0);         // End program if no file was declared
        }
        
        try {   // Check if the file actually exists
            BufferedReader reader = new BufferedReader( new FileReader ( commandLine[0] ) );    
        } 
        catch (FileNotFoundException e) {
            System.out.println( " Input Filename Not Found" );
            System.out.println( " Ending Program . . . \n" );
            System.exit(0);         // End program if no file was declared
        }
    }
    
    /**
     * Removes the non letter characters from the received String and returns that string
     * @ param  A string
     * @ return A string with the non letter characters removed
     */
    public String removeNonLetterChars(String word) {
    
    	// Temporary string will hold string with no letter chars
    	String tempWord = "";
	
	// Traverse the entire string
	while ( word.length() >=1 ) {
	
	    // Get the first letter of the word
	    String firstChar = word.substring(0, 1);
	    
	    // Update string minus first letter
	    word = word.substring(1, word.length() );
	    
	    //Add character to the new word only if it is a letter
	    if ( Character.isLetter( firstChar.charAt(0) ) ) {
	        tempWord = tempWord + firstChar;
	    }
	}
	
	// Returned string with no letter chars
	return tempWord;
	
    }    
            
    /**
     * Check if number in a given string is really a number and bigger than zero
     * @param   A string containing a numerical value
     * @return  A boolean value, true f string is a number and bigger than zero
     *                           false otherwise
     */
    public boolean isValidNumber(String str) {
        char[]c = str.toCharArray();    // An array of the chrarcter of the string
        
        // Check that every character is a number
        for ( int i = 0; i < str.length(); i ++ ) {
            if ( !Character.isDigit( c[i] ) ) {
                System.out.println(" Argument Is Not A Number");
                printInvalidCommand();
                return false;
            }
        }        
        
        int number = Integer.parseInt( str );   
        
        // Check if the number is bigger than zero
        if ( number < 1 ) {
            System.out.println(" Number not valid: Smaller than zero");
            printInvalidCommand();
            return false;
        }        
        return true;
    }

    /**
     * Print a invalid command message
     * @param   None
     * @return  None
     */
    public void printInvalidCommand() {
        System.out.println("Not Valid Command. Please Try Again. ");
    }    
}

0
1
分享到:
评论

相关推荐

    Go-trie-单词查找树实现Go实现

    Trie,又称为前缀树或字典树,是一种用于存储动态集合或关联数组的树形数据结构。它的主要特点是通过键的前缀来组织节点,从而快速进行前缀查询和模糊搜索。在Go语言中实现Trie,可以有效地支持字符串集合的增删查改...

    php-leetcode题解之实现Trie前缀树.zip

    Trie,也被称为字典树或前缀树,是一种用于存储字符串的数据结构,尤其适合进行高效的字符串查找。它的主要特点是能通过字典序的方式快速地查找具有相同前缀的字符串。Trie树的每个节点通常包含一个字符,并且有指向...

    java数组-基于java实现的双数组Trie树.zip

    本项目聚焦于利用Java实现的双数组Trie树,这是一种在字符串处理和搜索中广泛使用的数据结构。 Trie树,又称“前缀树”或“字典树”,是一种用于存储键值对的数据结构,特别适用于字符串。它的主要特点是能以O(1)的...

    Go-一个简单而快速的Go库用于将输入字符串模糊匹配到目标字符串列表

    而Trie树(也称前缀树)是一种用于高效存储和检索具有公共前缀的字符串的数据结构。 描述中的“一个简单而快速的Go库,用于将输入字符串模糊匹配到目标字符串列表”进一步强调了库的设计目标:简洁性和高性能。这...

    lua屏蔽字处理

    2. **Trie树(前缀树)**:构建一个Trie树,通过前缀匹配的方式快速判断输入字符串是否包含敏感词。Trie树适合处理大量且有公共前缀的敏感词,查找速度快且节省空间。 3. **动态规划**:可以使用动态规划算法,如...

    rust_sequence_trie:符合人体工程学的trie数据结构

    在IT领域,数据结构是构建高效算法的基础,而Trie(又称字典树或前缀树)作为一种特殊的数据结构,广泛应用于字符串相关的搜索和查找问题。`rust_sequence_trie`项目是一个用Rust编程语言实现的Trie数据结构库,其...

    数据结构算法及其实现

    - **堆**:一种特殊的树形数据结构,满足最大堆或最小堆性质,常用于优先队列和堆排序。 - **哈希表**:通过哈希函数快速查找元素,提供O(1)的平均查找时间,用于构建索引和缓存。 - **树**:包括二叉树、平衡树...

    模仿百度搜索模糊提示

    3. Trie树(字典树):Trie树是一种高效的前缀搜索数据结构,用于存储大量关键词,通过遍历树结构快速找到与输入字符匹配的关键词。 4. 缓存策略:为了提高响应速度,搜索提示系统通常会缓存近期或高频的搜索词,...

    应届生笔试-阿里巴巴笔试记

    - Trie树(也称为前缀树或字典树)是一种字符串检索数据结构,用于高效地查找具有公共前缀的字符串。 - 在Trie树中,每个节点代表一个字符串前缀,叶子节点代表完整字符串。 - 适用于关键词搜索、自动补全等功能...

    java源码:预输入搜索 Cleo.zip

    1. **Trie树**:Trie树是一种字符串查找的数据结构,每个节点代表一个前缀,通过节点间的连接表示字符串的关联。在Cleo中,Trie树用于存储关键词,当用户输入部分字符时,可以迅速找到所有匹配的完整词汇。Trie树的...

    Algorithm-liblpm.zip

    LPM算法的基本思想是通过构建一种数据结构,如字典树(Trie)、AC自动机(Aho-Corasick Automaton)或者Patricia树,来快速查找给定字符串的最长前缀。在字典树中,每个节点代表一个字符串的前缀,而边则表示字符的...

    包分类算法之一——TSS算法实现代码

    综上所述,TSS算法是一种高效的包分类方法,它利用了Trie数据结构的优势,使得在大量规则下,数据包的分类速度得以显著提高。通过理解和实现TSS算法,我们可以更好地理解网络流量管理的底层机制,以及如何通过编程...

    Go-go-wordsfilter是一个高性能的Go敏感词过滤器

    Trie树是一种字符串检索的数据结构,它通过节点之间的链接来表示前缀关系。每个节点包含一个字符,从根节点到任意节点的路径上经过的字符组合构成了一个字符串。在Go-go-wordsfilter中,每个敏感词都会被插入到这个...

    百度2012年实习生招聘笔试试题 -技术类

    **数据结构选择**:考虑到空间和时间效率,这里建议采用**Trie树**(前缀树)来存储字典中的所有单词。Trie树能够有效地支持快速查询以及插入操作。 2. **查询流程**: - 将字典中的每个单词插入到Trie树中。 - ...

    Auto-Completion-System-design:主要用于系统设计[电话簿搜索,字典,IP路由,最长前缀匹配,自动命令完成]

    在IT领域,自动完成系统是一种常见且至关重要的功能,它被广泛应用于各种场景,如电话簿搜索、字典查询、IP路由、最长前缀匹配以及命令行自动完成等。本项目"Auto-Completion-System-design"专注于这些领域的系统...

    LPM-Algorithms-Linux-XIA:该存储库由各种最长前缀匹配(LPM)算法组成,旨在为Linux-XIA找到最合适的算法

    最长前缀匹配(Longest Prefix Match, LPM)是路由查找中的核心算法,它在IP网络中用于确定数据包应被转发到哪个下一跳,基于其目的地IP地址的最长匹配前缀。这个存储库,"LPM-Algorithms-Linux-XIA",包含了多种...

    开源项目-hashicorp-go-memdb.zip

    它使用了先进的数据结构和算法,如B树和Trie树,确保了数据操作的高效性和一致性。 Go-MemDB的主要组件包括: 1. 数据表(Table):这是存储数据的基本单元,类似于传统数据库的表格。每个数据表都有自己的索引,...

    java程序敏感词分析

    5. **性能优化**:为了提高效率,可以考虑使用多线程处理大文本,或者使用并发数据结构如ConcurrentHashMap来存储敏感词库。 6. **异常处理**:在读取文件或处理用户输入时,应添加适当的错误处理机制,以应对可能...

    libzmq-v90-4_3_2-Visual Studio 9 2008.zip

    5. `unittest_mtrie.exe`:这可能是针对M-trie数据结构的单元测试,M-trie是一种优化的前缀树,用于快速查找和匹配前缀相同的元素,例如在网络地址中。 6. `unittest_udp_address.exe`:测试UDP地址处理的单元测试...

    基于Java的实例源码-预输入搜索 Cleo.zip

    这些数据结构能够快速地查找和匹配前缀,以生成实时的搜索建议。 2. **模糊匹配**:为了提供更准确的建议,Cleo可能实现了模糊匹配算法,如Levenshtein距离或Jaccard相似度,允许用户在输入不完全准确的情况下也能...

Global site tag (gtag.js) - Google Analytics