Вопрос:

Java Trie Matching с использованием итератора

java tree trie

318 просмотра

2 ответа

8 Репутация автора

У меня есть задание, которое включает в себя создание Trie названий компаний (считанных из файла), а затем чтение входных данных новостной статьи и подсчет количества случаев, когда название компании из Trie встречается в статье.

Я кодировал довольно стандартную структуру Trie, однако для назначения было более целесообразно, чтобы TrieNodes содержал полное слово, а не только каждый символ.

Чтобы усложнить задачу, каждое название компании из файла имеет одно «основное имя» и может иметь несколько «вторичных имен». Например: Microsoft Corporation, Microsoft, Xbox - где имя всегда является основным.

Задание требует, чтобы я посчитал все совпадения в статье для любого из названий компаний, но возвращал только основное имя компании при печати результатов. Из-за этого мой TrieNode имеет поле данных String primeName вместе со стандартным isEnd bool. Однако в моем случае isEnd представляет, формируют ли указанный узел и его родительский (ие) полное название компании.

Например, с вводом статьи «Корпорация Microsoft только что выпустила новую консоль Xbox». Мне нужно было бы вернуть что-то вроде «Microsoft: 2», потому что и Microsoft Corporation, и Xbox имеют одно и то же основное название компании - Microsoft.

Я использую итератор в методе getHits (), но когда я нахожу совпадение, мне нужно посмотреть на следующее слово в массиве, чтобы убедиться, что оно не является продолжением, прежде чем я решу, останавливаться или продолжать. Проблема состоит в том, что вызов iter.next () не просто «просматривает» следующее значение, но он движется вперед, по сути, заставляя меня пропускать слова.

Например, если вы посмотрите на приведенный ниже код и мой пример, после того, как «Best» получает удар, он должен увидеть, что «Buy» является дочерним, и в следующий раз, когда он зацикливается, получит совпадение с «Buy», но так как я уже вызовите iter.next (), чтобы посмотреть на «Buy» в цикле while, следующая итерация полностью пропускает «Buy». Есть ли какой-то способ, которым я могу просто посмотреть на следующее значение iter в цикле While, фактически не переходя к нему? Кроме того, любые улучшения этого кода приветствуются! Я уверен, что есть много мест, где я что-то небрежно реализовал.

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BuildTrie {


    // Class Methods
    public static void main(String[] args) throws IOException {

        Trie Companies = new Trie();

        String filename = "companies.dat";
        try {
            BufferedReader reader = new BufferedReader(new FileReader(filename));
            String line;
            while ((line = reader.readLine()) != null) {
                // Split line by tab character
                String[] aliases = line.replaceAll("\\p{P}", "").split("\t");
                // Loop over each "alias" of specific company
                for (int n = 0; n < aliases.length; n++) {
                    String[] name = aliases[n].split(" ");
                    // Insert each alias into Trie with index 0 as primary
                    Companies.insert(name, aliases[0]);
                }

            }
            reader.close();
        } catch (Exception e) {
            System.err.format("Exception occurred trying to read '%s'.", filename);
            e.printStackTrace();
        }
        /*System.out.println("Article Input: ");
        try (BufferedReader input = new BufferedReader(new InputStreamReader(System.in))) {
            String line;
            while ((line = input.readLine()) != null) {
                if (".".equals(line)) break;
                String[] items = line.trim().replaceAll("\\p{P}", "").split("\\s+");
                for (int i = 0; i < items.length; i++) {
                    Companies.words.add(items[i]);
                    //System.out.println(items[i]);
                }
            }
        }*/

        Companies.articleAdd("The");
        Companies.articleAdd("company");
        Companies.articleAdd("Best");
        Companies.articleAdd("Buy");
        Companies.articleAdd("sell");
        Companies.articleAdd("Xbox");

        Companies.getHits();

    }

}

// Trie Node, which stores a character and the children in a HashMap
class TrieNode {
    // Data Fields
    private String word;
    HashMap<String,TrieNode> children;
    boolean bIsEnd;
    private String primary = "";

    // Constructors
    public TrieNode() {
        children = new HashMap<>();
        bIsEnd = false;
    }
    public TrieNode(String st, String prime)  {
        word = st;
        children = new HashMap<>();
        bIsEnd = false;
        primary = prime;
    }

    // Trie Node Methods
    public HashMap<String,TrieNode> getChildren() {
        return children;
    }
    public String getValue() {
        return word;
    }
    public void setIsEnd(boolean val) {
        bIsEnd = val;
    }
    public boolean isEnd() {
        return bIsEnd;
    }
    public String getPrime() {
        return primary;
    }
}

class Trie {
    private ArrayList<String> article = new ArrayList<String>();
    private HashMap<String,Integer> hits = new HashMap<String,Integer>();

    // Constructor
    public Trie() {
        root = new TrieNode();
    }

    // Insert article text
    public void articleAdd(String word) {
        article.add(word);
    }

    // Method to insert a new company name to Trie
    public void insert(String[] names, String prime)  {

        // Find length of the given name
        int length = names.length;
        //TrieNode currNode = root;

        HashMap<String,TrieNode> children = root.children;

        // Traverse through all words of given name
        for( int i=0; i<length; i++)
        {
            String name = names[i];
            System.out.println("Iter: " + name);
            TrieNode t;
            // If there is already a child for current word of given name
            if( children.containsKey(name))
                t = children.get(name);
            else   // Else create a child
            {
                System.out.println("Inserting node " + name + " prime is " + prime);
                t = new TrieNode(name, prime);
                children.put( name, t );
            }
            children = t.getChildren();

            int j = names.length-1;
            if(i==j){
                t.setIsEnd(true);
                System.out.println("WordEnd");
            }
        }
    }

    public void getHits() {
        // String[] articleArr = article.toArray(new String[0]);
        // Initialize reference to traverse through Trie
        // TrieNode crawl = root;
        // int level, prevMatch = 0;
        Iterator<String> iter = article.iterator();
        TrieNode currNode = root;

        while (iter.hasNext()) {
            String word = iter.next();
            System.out.println("Iter: " + word);
            // HashMap of current node's children
            HashMap<String,TrieNode> child = currNode.getChildren();
            // If hit in currNode's children
            if (child.containsKey(word)) {
                System.out.println("Node exists: " + word);
                // Update currNode to be node that matched
                currNode = child.get(word);
                System.out.println(currNode.isEnd());
                String next = "";
                // If currNode is leaf and next node has no match in children, were done
                if (iter.hasNext()) {next = iter.next();}
                if (currNode.isEnd() && !child.containsKey(next)) {
                        System.out.println("Matched word: " + word);
                        System.out.println("Primary: " + currNode.getPrime());
                        currNode = root;
                    } else {
                    // Else next node is continuation

                }

            } else {
             // Else ignore next word and reset

                currNode = root;
            }
        }
    }
    private TrieNode root;
}
Автор: John Kelly Источник Размещён: 22.08.2016 08:46

Ответы (2)


0 плюса

1257 Репутация автора

Я думаю, что вместо использования while и iter.next () вы можете использовать для цикла, как показано ниже

for (запись Map.Entry: article.entrySet ()) {String word = entry.getKey ();

}

Таким образом, вы на самом деле не переходите к следующим элементам вашей хэш-карты.

Если это не ваша точка зрения, пожалуйста, уточните нам.

Спасибо нгиа

Автор: Nghia Do Размещён: 23.08.2016 04:46

0 плюса

8 Репутация автора

Для этого я решил использовать стиль цикла for вместо цикла While, а также настроил некоторую логику, чтобы заставить его работать. Для тех, кто заинтересован, ниже приведен новый код, а также пример файла «companies.dat» (который заполняется в Trie). Stdin - это любой текстовый отрывок, который заканчивается на "." на новой линии.

Companies.dat:

Microsoft Corporation   Microsoft   Xbox
Apple Computer  Apple   Mac
Best Buy
Dell

TrieBuilder:

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BuildTrie {

    // Class Methods
    public static void main(String[] args) throws IOException {

        Trie Companies = new Trie();

        String filename = "companies.dat";
        try {
            BufferedReader reader = new BufferedReader(new FileReader(filename));
            String line;
            while ((line = reader.readLine()) != null) {
                // Split line by tab character
                String[] aliases = line.replaceAll("\\p{P}", "").split("\t");
                // Loop over each "alias" of specific company
                for (int n = 0; n < aliases.length; n++) {
                    String[] name = aliases[n].split(" ");
                    // Insert each alias into Trie with index 0 as primary
                    Companies.insert(name, aliases[0]);
                }

            }
            reader.close();
        } catch (Exception e) {
            System.err.format("Exception occurred trying to read '%s'.", filename);
            e.printStackTrace();
        }
        System.out.println("Article Input: ");
        try (BufferedReader input = new BufferedReader(new InputStreamReader(System.in))) {
            String line;
            while ((line = input.readLine()) != null) {
                if (".".equals(line)) break;
                String[] items = line.trim().replaceAll("\\p{P}", "").split("\\s+");
                for (int i = 0; i < items.length; i++) {
                    Companies.articleAdd(items[i]);
                }
            }
        }

        Companies.getHits();

    }

}

// Trie Node, which stores a character and the children in a HashMap
class TrieNode {
    // Data Fields
    private String word;
    HashMap<String,TrieNode> children;
    boolean bIsEnd;
    private String primary = "";

    // Constructors
    public TrieNode() {
        children = new HashMap<>();
        bIsEnd = false;
    }
    public TrieNode(String st, String prime)  {
        word = st;
        children = new HashMap<>();
        bIsEnd = false;
        primary = prime;
    }

    // Trie Node Methods
    public HashMap<String,TrieNode> getChildren() {
        return children;
    }
    public String getValue() {
        return word;
    }
    public void setIsEnd(boolean val) {
        bIsEnd = val;
    }
    public boolean isEnd() {
        return bIsEnd;
    }
    public String getPrime() {
        return primary;
    }
}

class Trie {
    private ArrayList<String> article = new ArrayList<String>();
    private HashMap<String,Integer> hits = new HashMap<String,Integer>();

    // Constructor
    public Trie() {
        root = new TrieNode();
    }

    // Insert article text
    public void articleAdd(String word) {
        article.add(word);
    }

    // Method to insert a new company name to Trie
    public void insert(String[] names, String prime)  {

        // Find length of the given name
        int length = names.length;

        HashMap<String,TrieNode> children = root.children;

        // Traverse through all words of given name
        for( int i=0; i<length; i++)
        {
            String name = names[i];
            TrieNode t;
            // If there is already a child for current word of given name
            if( children.containsKey(name))
                t = children.get(name);
            else   // Else create a child
            {
                t = new TrieNode(name, prime);
                children.put( name, t );
            }
            children = t.getChildren();

            int j = names.length-1;
            if(i==j){
                t.setIsEnd(true);
            }
        }
    }

    public void getHits() {
        // Initialize reference to traverse through Trie
        TrieNode currNode = root;

        for (int i=0; i < article.size(); i++) {
            String word = article.get(i);
            System.out.println("Searching: " + word);
            // HashMap of current node's children
            HashMap<String, TrieNode> child = currNode.getChildren();
            // If hit in currNode's children
            if (child.containsKey(word)) {
                System.out.println("Node exists: " + word);
                // Update currNode to be node that matched
                currNode = child.get(word);
                child = currNode.getChildren();
                System.out.println("isEnd?: " + currNode.isEnd());
                String next = "";
                if (i+1 < article.size()) {
                    next = article.get(i+1);
                }
                // If currNode is leaf and next node has no match in children, were done
                if (currNode.isEnd() && !child.containsKey(next)) {
                    System.out.println("Primary of match: " + currNode.getPrime());
                    currNode = root;
                }
            } else {
                // Else ignore next word and reset
                System.out.println("No match.");
                currNode = root;
            }
        }
    }
    private TrieNode root;
}
Автор: John Kelly Размещён: 23.08.2016 05:22
Вопросы из категории :
32x32