会社名のTrieを作成して(ファイルから読み込み)、ニュース記事の入力を読み込み、Trieの会社名が記事に含まれている回数を数えるという課題があります。Java Trie Iteratorを使用したマッチング
私はかなり標準的なTrie構造をコーディングしましたが、割り当てのために、TrieNodesに各文字ではなく完全な単語を保持させるのがより理にかなっていました。
さらに複雑にするために、ファイルの各企業名には「プライマリ名」が1つあり、複数の「セカンダリ名」を持つことができます。例:Microsoft Corporation、Microsoft、Xbox - 名は常にプライマリです。
割り当てでは、会社名のいずれかの記事のすべての一致をカウントする必要がありますが、結果を印刷するときには会社のプライマリ名のみが返されます。このため、私のTrieNodeには、標準のisEnd boolとともに、文字列primeNameデータフィールドがあります。しかし、私の場合、isEndは指定されたノードとその親が完全な会社名を形成するかどうかを表します。
たとえば、「Microsoft Corporationは新しいXboxコンソールをリリースしました」という記事を入力します。 Microsoft CorporationとXboxの両方がMicrosoftと同じ主要企業名を共有しているため、「Microsoft:2」の行に沿って何かを返す必要があります。
getHits()メソッドでイテレータを使用していますが、ヒットした場合は、配列内の次の単語を調べて、停止するか続行するかを決める前に継続していないことを確認する必要があります。問題は、iter.next()を呼び出すだけで次の値を "覗く"のではなく、前方に移動し、本質的に私が単語をスキップすることです。
たとえば、「Best」がヒットした後、「Buy」が子供で、次回にループして「Buy」を試合したときに、 Whileループ内で "Buy"を見るためにiter.next()を呼び出すので、次の反復では "Buy"は完全にスキップされます。 Whileループ内の次のiter値を実際に移動することなく単に調べることができる方法はありますか?また、このコードを改善していただければ幸いです!私は何かを怠惰に実行する場所がたくさんあると確信しています。
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;
}
おかげNghia、私は実際に予想通り、右投稿した後、(私のロジックにいくつかのマイナーな改良で)働いているように見えることを試みました。 –