التنفيذ Trie.
https://stackoverflow.com/questions/2225540
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أحاول تنفيذ ثلاثي بسيط جدا في جافا يدعم 3 عمليات. أود أن يكون لديك طريقة إدراج، وهي طريقة (IE هي كلمة معينة في Trie)، وسيلة Tostring لإرجاع النموذج Trie In String. أعتقد أن لدي إدراج يعمل بشكل صحيح، لكنه يثبت أن يكون صعبا. إليك ما لدي حتى الآن.
الطبقة الثلاثية.
public class CaseInsensitiveTrie implements SimpleTrie {
//root node
private TrieNode r;
public CaseInsensitiveTrie() {
r = new TrieNode();
}
public boolean has(String word) throws InvalidArgumentUosException {
return r.has(word);
}
public void insert(String word) throws InvalidArgumentUosException {
r.insert(word);
}
public String toString() {
return r.toString();
}
public static void main(String[] args) {
CaseInsensitiveTrie t = new CaseInsensitiveTrie();
System.out.println("Testing some strings");
t.insert("TEST");
t.insert("TATTER");
System.out.println(t.has("TEST"));
}
}
وفئة العقدة
public class TrieNode {
//make child nodes
private TrieNode[] c;
//flag for end of word
private boolean flag = false;
public TrieNode() {
c = new TrieNode[26]; //1 for each letter in alphabet
}
protected void insert(String word) {
int val = word.charAt(0) - 64;
//if the value of the child node at val is null, make a new node
//there to represent the letter
if (c[val] == null) {
c[val] = new TrieNode();
}
//if word length > 1, then word is not finished being added.
//otherwise, set the flag to true so we know a word ends there.
if (word.length() > 1) {
c[val].insert(word.substring(1));
} else {
c[val].flag = true;
}
}
public boolean has(String word) {
int val = word.charAt(0) - 64;
if (c[val]!=null && word.length()>1) {
c[val].has(word.substring(1));
} else if (c[val].flag==true && word.length()==1) {
return true;
}
return false;
}
public String toString() {
return "";
}
}
في الأساس، عند إنشاء Trie، يتم إنشاء ثلاثية الأبعاد كجذر مع 26 طفلا. عند محاولة إدراج، يتم استدعاء INSERT على عقدة الجذر هذه، والتي تنشئ عقدة جديدة بشكل متكرر في الموضع الصحيح، وتستمر حتى تكتمل الكلمة. أعتقد أن هذه الطريقة تعمل بشكل صحيح.
بلدي وظيفة مكسورة جدا، لأنني يملك أن يكون هذا بيان العودة خارج بين قوسين لسبب ما. لا يمكنني احتواءها داخل جملة أخرى أو يشكو المترجم. بخلاف ذلك، أعتقد أن الطريقة يجب أن تعمل مع بعض القرص، لكنني لا أستطيع معرفة ذلك مدى الحياة.
ToString هو الوحش الذي حاولت معالجته، ولكن لا شيء أرمي فيه يعمل، لذلك سأترك ذلك حتى أحلل مشكلة. إذا حصلت على عمل قد أكون قادرا على معرفة وسيلة لإعادة تهيئة ذلك إلى وظيفة ToString.
الغرض من INT VAL = Word.charat (0) - 64؛ . لأن كل سلسلة تم إدخالها يجب أن تكون كل قبعات (سأقوم بإنشاء وظيفة تنسيق سلسلة للتأكد من ذلك بعد ذلك)، وبالتالي فإن القيمة الأولى للحرف الأول - 64 ستكون موضعها في الصفيف. IE مؤشر الصفيف 0 هو، لذلك A = 64، A - 64 = 0. B = 65، B - 64 = 1، وهلم جرا.
المحلول
لك has يجب أن تبدو الوظيفة مثل هذا:
if (c[val]!=null && word.length()>1) {
return c[val].has(word.substring(1)); //<-- Change is on this line
} else if (c[val].flag==true && word.length()==1) {
...etc
يمكنك إجراء مكالمة متكررة، لكنك تحتاج حقا إلى السماح هذه القيمة تنتشر إلى المتصل الأصلي.
نصائح أخرى
ربما يمكنك فقط استخدام "خريطة C" بدلا من "Trienode [] C"، والتي من شأنها أن تسمح لك باستخدام هذا لجميع أنواع الأحرف الكبيرة / الصغيرة وحتى الأحرف الخاصة وحتى سيوفر لك مساحة (تخصيص مجموعة الأحرف 26 كل مستوى حرف)
هنا هو تطبيقي: -
public class Tries {
class Node {
HashMap<Character, Node> children;
boolean end;
public Node(boolean b){
children = new HashMap<Character, Tries.Node>();
end = false;
}
}
private Node root;
public Tries(){
root = new Node(false);
}
public static void main(String args[]){
Tries tr = new Tries();
tr.add("dog");
tr.add("doggy");
System.out.println(tr.search("dogg"));
System.out.println(tr.search("doggy"));
}
private boolean search(String word) {
Node crawl = root;
int n = word.length();
for(int i=0;i<n;i++){
char ch = word.charAt(i);
if(crawl.children.get(ch) == null){
return false;
}
else {
crawl = crawl.children.get(ch);
if(i==n-1 && crawl.end == true){
return true;
}
}
}
return false;
}
private void add(String word) {
Node crawl = root;
int n = word.length();
for(int i=0;i<n;i++){
char ch = word.charAt(i);
if(crawl.children.containsKey(ch)){
crawl = crawl.children.get(ch);
}
else {
crawl.children.put(ch, new Node(false));
Node temp = crawl.children.get(ch);
if(i == n-1){
temp.end = true;
}
crawl = temp;
System.out.println(ch + " " + crawl.end);
}
}
}
}
هنا تنفيذي:
public class Tries {
private static class Leaf {
private Leaf(char c) {
this.c=c;
}
char c;
int counter = 1;
List<Leaf> leaves = new ArrayList<>(10);
}
private Leaf root = new Leaf('0');
public void add(String word) {
Leaf current = root;
Leaf newLeaf = null;
for (char c : word.toCharArray()) {
boolean found = false;
for (Leaf leaf : current.leaves) {
if (leaf.c == c) {
current = leaf;
current.counter++;
found=true;
break;
}
}
if (!found) {
newLeaf = new Leaf(c);
current.leaves.add(newLeaf);
current = newLeaf;
}
}
}
public int find(String partial) {
Leaf current = root;
for (char c : partial.toCharArray()) {
boolean found = false;
for (Leaf leaf : current.leaves) {
if (leaf.c == c) {
current=leaf;
found=true;
break;
}
}
if(!found) return 0;
}
return current.counter;
}
public boolean hasWord(String partial) {
return find(partial)>0;
}
}
هنا تطبيق جافا بسيط دون استخدام أي بنية بيانات أخرى
import java.util.ArrayList;
import java.util.List;
class Trie {
private static Node root = new Node(' ', false);
static int getIndex(char x) {
return ((int) x) - ((int) 'a');
}
static class Node {
char data;
boolean isLeaf;
Node[] children;
Node(char data, boolean leaf) {
this.data = data;
this.isLeaf = leaf;
this.children = new Node[26];
}
}
static void insert(String data, Node root) {
if (data == null || data.length() == 0) {
return;
}
Node child = root.children[getIndex(data.charAt(0))];
if (child == null) {
Node node = new Node(data.charAt(0), data.length() == 1);
root.children[getIndex(data.charAt(0))] = node;
if (data.length() > 1) {
insert(data.substring(1, data.length()), node);
}
} else {
if (data.length() == 1) {
child.isLeaf = true;
} else {
insert(data.substring(1, data.length()), child);
}
}
}
static boolean find(String data, Node root) {
if (data == null || data.length() == 0) {
return true;
}
char x = data.charAt(0);
//note that first node ie root is just dummy, it just holds important
Node node = root.children[getIndex(x)];
if (node == null) {
return false;
} else {
if (data.length() == 1) {
return node.isLeaf;
} else {
return find(data.substring(1, data.length()), node);
}
}
}
static boolean delete(String data, Node root) {
if (data == null || data.length() == 0) {
return false;
}
char x = data.charAt(0);
//note that first node ie root is just dummy, it just holds important
Node node = root.children[getIndex(x)];
if (node == null) {
return false;
} else {
if (data.length() == 1) {
node.isLeaf = false;
boolean allNull = true;
for (Node node1 : node.children) {
allNull = allNull && node1 == null;
}
return allNull;
} else {
boolean delete = delete(data.substring(1, data.length()), node);
if (delete) {
node.children[getIndex(x)] = null;
if(node.isLeaf){
return false;
}
boolean allNull = true;
for (Node node1 : node.children) {
allNull = allNull && node1 == null;
}
return allNull; }
}
}
return false;
}
private static List<String> strings = new ArrayList<>();
private static List<String> getAll() {
strings = new ArrayList<String>();
findAllDFS(root, "");
return strings;
}
private static void findAllDFS(Node node, String old) {
if (node != null) {
if (node.data != ' ') {
old = old + node.data;
}
if (node.isLeaf) {
strings.add(old);
}
for (Node node1 : node.children) {
findAllDFS(node1, old);
}
}
}
public static void main(String[] args) {
insert("abc", root);
insert("xyz", root);
insert("abcd", root);
insert("abcde", root);
delete("abcd", root);
/* System.out.println(find("abc", root));
System.out.println(find("abcd", root));
System.out.println(find("ab", root));
System.out.println(find("xyz", root));*/
System.out.println(getAll());
}
}
