Trie数据结构的插入和压缩实现，使用Java并发哈希映射。

huangapple
未分类评论42阅读模式
英文:

Trie Data Structure Insertion and Compression implementation in Java using Concurrent Hash Map

问题

以下是您提供的代码的翻译部分：

尝试实现 Trie 数据结构添加元素，然后尝试通过 Trie 压缩机制来减少它。由于特定的用例，实现进入无限循环，可能需要查看一下，看看什么是可能的最佳基本条件。

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

public class TrieNode {
    
    private String value;
    private ConcurrentHashMap<String, TrieNode> children;
    private boolean isWord;
    
    public TrieNode(String value){
        this.value = value;
        this.children = new ConcurrentHashMap<String, TrieNode>();
    }
    
    public static void sortbykey(ConcurrentHashMap<String, TrieNode> map) {
        ArrayList<String> sortedKeys = new ArrayList<String>(map.keySet());
        
        Collections.sort(sortedKeys);
    
    }
    
    public static ArrayList<TrieNode> hashMapValues (ConcurrentHashMap<String, TrieNode> map) {
        ArrayList<TrieNode> nodeList = new ArrayList<TrieNode>(map.values());
        return nodeList;
    }
    
    public ArrayList<TrieNode> getChildren() {
        sortbykey(this.children);
        return hashMapValues(this.children);
    }
    
    public ConcurrentHashMap<String, TrieNode> getChildrenMappings()
    {
        return this.children;
    }
    
    public void addChild(int numCharacters, String value)
    {
        // 如果已经到达根级别
        if(value.length() == numCharacters)
        {
            this.isWord = true;
        }
        // 如果值仍有更多字符，则添加一个子节点
        else
        {
            TrieNode nextNode = null;
            String nextCharacter = Character.toString(value.charAt(numCharacters));
            if(this.children.get(nextCharacter) == null)
            {
                String nextPrefix = value.substring(0, numCharacters + 1);
                nextNode = new TrieNode(nextPrefix);
                this.children.put(nextCharacter, nextNode);
            }
            numCharacters++;
            
            this.children.get(nextCharacter).addChild(numCharacters, value);
        }
        
    }
    
    
    public void reduce(){
            
            for(ConcurrentHashMap.Entry<String, TrieNode> child : this.children.entrySet()){
                
                child.getValue().reduce();
                
                // 清除原始子节点映射
                this.children.remove(child.getKey());

                // 用可能包含多个字符的新映射替换，如果我的子节点与其他子节点合并
                String newMapping = child.getValue().getValue().substring(this.getValue().length());
                                
                this.children.put(newMapping, child.getValue());
                
            }
            
            if(this.children.size() == 1){
                                
                for(ConcurrentHashMap.Entry<String, TrieNode> child : this.children.entrySet()){
                    
                    // 如果我只有一个子节点，如果我自己不是一个单词，就用他的子节点替换我
                    if(!this.isWord()){
                        
                        // 清除额外的子节点
                        this.children.remove(child.getKey());
                        
                        // 获取子节点的值、单词状态和子节点
                        this.setValue(child.getValue().getValue());
                        this.setIsWord(child.getValue().isWord());
                        
                        for(ConcurrentHashMap.Entry<String, TrieNode> grandchild : child.getValue().getChildrenMappings().entrySet()){
                            this.children.put(grandchild.getKey(), grandchild.getValue());
                        }
                        
                    }
                }
                
            }
            
    }
    
    public boolean isWord()
    {
        return this.isWord;
    }
    
    public void setIsWord(boolean isWord){
        this.isWord = isWord;
    }
    
    public String getValue()
    {
        return this.value;
    }
    
    public void setValue(String newValue){
        this.value = newValue;
    }
    
    public static void main(String[] args){
        
        
        TrieNode tN = new TrieNode("");

        
        tN.addChild(0, "www.corriere.it/27esimaora/laquila");
        tN.addChild(0, "www.corriere.it/27esimaora");
        tN.addChild(0, "www.corriere.it/cronache/sesso-e-amore/");
        tN.addChild(0, "www.corriere.it/foto-gallery/cronache/sesso-e-amore/");
        
        tN.reduce();        
        
        ConcurrentHashMap<String, TrieNode> childrenMappings = tN.getChildren().get(0).getChildren().get(0).getChildren().get(0).getChildrenMappings();
        
        
        for(Map.Entry<String, TrieNode> children : childrenMappings.entrySet()){
            
            System.out.println(children.getKey() + " = " + children.getValue().getChildrenMappings() + children.getValue().getValue() + " " + children.getValue().isWord);
            
            
        }
        
        System.out.println(tN.getChildren());
    }
}

请注意，翻译是基于您提供的代码进行的，保留了代码结构和注释。如果您对翻译有任何疑问，请随时提问。

英文:

Trying to implement Trie data structure addition of elements and then trying to to reduce it as trie compression mechanism. There is a specific use case due to which the implementation is running forever as an infinite loop, may we have a look at it and see what could be the best possible base condition for that.

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

public class TrieNode {
	
	private String value;
	private ConcurrentHashMap&lt;String, TrieNode&gt; children;
	private boolean isWord;
	
	public TrieNode(String value){
		this.value = value;
		this.children = new ConcurrentHashMap&lt;String, TrieNode&gt;();
	}
	
	public static void sortbykey(ConcurrentHashMap&lt;String, TrieNode&gt; map) {
		ArrayList&lt;String&gt; sortedKeys = new ArrayList&lt;String&gt;(map.keySet());
		
		Collections.sort(sortedKeys);
	
	}
	
	public static ArrayList&lt;TrieNode&gt; hashMapValues (ConcurrentHashMap&lt;String, TrieNode&gt; map) {
		ArrayList&lt;TrieNode&gt; nodeList = new ArrayList&lt;TrieNode&gt;(map.values());
		return nodeList;
	}
	
	public ArrayList&lt;TrieNode&gt; getChildren() {
		sortbykey(this.children);
		return hashMapValues(this.children);
	}
	
	public ConcurrentHashMap&lt;String, TrieNode&gt; getChildrenMappings()
	{
		return this.children;
	}
	
	public void addChild(int numCharacters,String value)
	{
		//If we have arrived at the root level
		if(value.length() == numCharacters)
		{
			this.isWord = true;
		}
		//If the value still has more characters then add a child
		else
		{
			TrieNode nextNode = null;
			String nextCharacter = Character.toString(value.charAt(numCharacters));
			if(this.children.get(nextCharacter)==null)
			{
				String nextPrefix = value.substring(0,numCharacters+1);
				nextNode = new TrieNode(nextPrefix);
				this.children.put(nextCharacter, nextNode);
			}
			numCharacters++;
			
			this.children.get(nextCharacter).addChild(numCharacters,value);
		}
		
	}
	
	
    public void reduce(){
    		
    			for(ConcurrentHashMap.Entry&lt;String,TrieNode&gt; child : this.children.entrySet()){
    				
    				child.getValue().reduce();
    				
    				//Get rid of original child mapping
    				this.children.remove(child.getKey());

    				//Replace with a new mapping which may include multiple characters if my child has been combined with other children
    				String newMapping = child.getValue().getValue().substring(this.getValue().length());
    				    				
    	            this.children.put(newMapping, child.getValue());
    	            
    			}
    			
    			if(this.children.size() == 1){
    				    				
    				for(ConcurrentHashMap.Entry&lt;String,TrieNode&gt; child : this.children.entrySet()){
    		            
    					//If I only have a single child, replace it with his children if I&#39;m not also a word on my own
    					if(!this.isWord()){
    						
    						//Get rid of the extra child node
    						this.children.remove(child.getKey());
    						
    						//Take the child nodes value, word status and children
    						this.setValue(child.getValue().getValue());
    						this.setIsWord(child.getValue().isWord());
    						
    						for(ConcurrentHashMap.Entry&lt;String,TrieNode&gt; grandchild : child.getValue().getChildrenMappings().entrySet()){
    							this.children.put(grandchild.getKey(),grandchild.getValue());
    						}
    						
    					}
    				}
    				
    			}
    			
	}
	
	public boolean isWord()
	{
		return this.isWord;
	}
	
	public void setIsWord(boolean isWord){
		this.isWord = isWord;
	}
	
	public String getValue()
	{
		return this.value;
	}
	
	public void setValue(String newValue){
		this.value = newValue;
	}
	
	public static void main(String[] args){
		
		
		TrieNode tN = new TrieNode(&quot;&quot;);
		
		
		tN.addChild(0, &quot;www.corriere.it/27esimaora/laquila&quot;);
		tN.addChild(0, &quot;www.corriere.it/27esimaora&quot;);
		tN.addChild(0, &quot;www.corriere.it/cronache/sesso-e-amore/&quot;);
		tN.addChild(0, &quot;www.corriere.it/foto-gallery/cronache/sesso-e-amore/&quot;);
		
		tN.reduce();		
		
		ConcurrentHashMap&lt;String, TrieNode&gt; childrenMappings = tN.getChildren().get(0).getChildren().get(0).getChildren().get(0).getChildrenMappings();
		
		
		for(Map.Entry&lt;String, TrieNode&gt; children : childrenMappings.entrySet()){
			
			System.out.println(children.getKey() + &quot; = &quot; + children.getValue().getChildrenMappings() + children.getValue().getValue() + &quot; &quot;+ children.getValue().isWord);
			
			
		}
		
		System.out.println(tN.getChildren());
	}
}

答案1

得分: 0

我修改了你的代码，并添加了一个条件：只有当新映射不等于当前子节点时，才会删除当前子节点并添加新的映射。

我还不确定你最后想要打印什么内容。因此我添加了我的打印语句。

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

class TrieNode {

    private String value;
    private ConcurrentHashMap<String, TrieNode> children;
    private boolean isWord;

    public TrieNode(String value){
        this.value = value;
        this.children = new ConcurrentHashMap<String, TrieNode>();
    }

    public static void sortbykey(ConcurrentHashMap<String, TrieNode> map) {
        ArrayList<String> sortedKeys = new ArrayList<String>(map.keySet());

        Collections.sort(sortedKeys);
    }

    public static ArrayList<TrieNode> hashMapValues (ConcurrentHashMap<String, TrieNode> map) {
        ArrayList<TrieNode> nodeList = new ArrayList<TrieNode>(map.values());
        return nodeList;
    }

    public ArrayList<TrieNode> getChildren() {
        sortbykey(this.children);
        return hashMapValues(this.children);
    }

    public ConcurrentHashMap<String, TrieNode> getChildrenMappings()
    {
        return this.children;
    }

    public void addChild(int numCharacters,String value)
    {
        //If we have arrived at the root level
        if(value.length() == numCharacters)
        {
            this.isWord = true;
        }
        //If the value still has more characters then add a child
        else
        {
            TrieNode nextNode = null;
            String nextCharacter = Character.toString(value.charAt(numCharacters));
            if(this.children.get(nextCharacter)==null)
            {

                String nextPrefix = value.substring(0,numCharacters+1);
                nextNode = new TrieNode(nextPrefix);
                this.children.put(nextCharacter, nextNode);
            }
            numCharacters++;

            this.children.get(nextCharacter).addChild(numCharacters,value);
        }

    }


    public void reduce(){

        for(ConcurrentHashMap.Entry<String,TrieNode> child : this.children.entrySet()){

            child.getValue().reduce();

            //Get rid of original child mapping
            //this.children.remove(child.getKey());

            //Replace with a new mapping which may include multiple characters if my child has been combined with other children
            String newMapping = child.getValue().getValue().substring(this.getValue().length());

            // only if the new mapping is not equal.
            if (!newMapping.equals(child.getKey())) {
                this.children.remove(child.getKey());
                this.children.put(newMapping, child.getValue());
            }
            //this.children.put(newMapping, child.getValue());

        }

        if(this.children.size() == 1){

            for(ConcurrentHashMap.Entry<String,TrieNode> child : this.children.entrySet()){

                //If I only have a single child, replace it with his children if I'm not also a word on my own
                if(!this.isWord()){

                    //Get rid of the extra child node
                    this.children.remove(child.getKey());

                    //Take the child nodes value, word status and children
                    this.setValue(child.getValue().getValue());
                    this.setIsWord(child.getValue().isWord());
                    for(ConcurrentHashMap.Entry<String,TrieNode> grandchild : child.getValue().getChildrenMappings().entrySet()){
                        this.children.put(grandchild.getKey(),grandchild.getValue());
                    }

                }
            }

        }

    }

    public boolean isWord()
    {
        return this.isWord;
    }

    public void setIsWord(boolean isWord){
        this.isWord = isWord;
    }

    public String getValue()
    {
        return this.value;
    }

    public void setValue(String newValue){
        this.value = newValue;
    }

    public static void main(String[] args){

        TrieNode tN = new TrieNode("");

        tN.addChild(0, "www.corriere.it/27esimaora/laquila");
        tN.addChild(0, "www.corriere.it/27esimaora");
        tN.addChild(0, "www.corriere.it/cronache/sesso-e-amore/");
        tN.addChild(0, "www.corriere.it/foto-gallery/cronache/sesso-e-amore/");

        tN.reduce();

        System.out.println(" root " + tN.getValue());
        System.out.println(" first level child 1 " + tN.getChildren().get(0).getValue());
        System.out.println(" first level child 2 " + tN.getChildren().get(1).getValue());
        System.out.println(" second level child 1 " + tN.getChildren().get(1).getChildren().get(0).getValue());
        System.out.println(" first level child 3 " + tN.getChildren().get(2).getValue());

        /*ConcurrentHashMap<String, TrieNode> childrenMappings = tN.getChildren().get(0).getChildren().get(0).getChildren().get(0).getChildrenMappings();

        for(Map.Entry<String, TrieNode> children : childrenMappings.entrySet()){

            System.out.println(children.getKey() + " = " + children.getValue().getChildrenMappings() + children.getValue().getValue() + " "+ children.getValue().isWord);

        }

        System.out.println(tN.getChildren());
        */
    }
}
英文:

I modified your code and added a condition that only if the new mapping not equal to the current child, then only remove the current child and add the new mapping.

I was also not sure what you were trying to print in the end. Therefore I have added my print statements.

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

class TrieNode {

    private String value;
    private ConcurrentHashMap&lt;String, TrieNode&gt; children;
    private boolean isWord;

    public TrieNode(String value){
        this.value = value;
        this.children = new ConcurrentHashMap&lt;String, TrieNode&gt;();
    }

    public static void sortbykey(ConcurrentHashMap&lt;String, TrieNode&gt; map) {
        ArrayList&lt;String&gt; sortedKeys = new ArrayList&lt;String&gt;(map.keySet());

        Collections.sort(sortedKeys);

    }

    public static ArrayList&lt;TrieNode&gt; hashMapValues (ConcurrentHashMap&lt;String, TrieNode&gt; map) {
        ArrayList&lt;TrieNode&gt; nodeList = new ArrayList&lt;TrieNode&gt;(map.values());
        return nodeList;
    }

    public ArrayList&lt;TrieNode&gt; getChildren() {
        sortbykey(this.children);
        return hashMapValues(this.children);
    }

    public ConcurrentHashMap&lt;String, TrieNode&gt; getChildrenMappings()
    {
        return this.children;
    }

    public void addChild(int numCharacters,String value)
    {
        //If we have arrived at the root level
        if(value.length() == numCharacters)
        {
            this.isWord = true;
        }
        //If the value still has more characters then add a child
        else
        {
            TrieNode nextNode = null;
            String nextCharacter = Character.toString(value.charAt(numCharacters));
            if(this.children.get(nextCharacter)==null)
            {

                String nextPrefix = value.substring(0,numCharacters+1);
                nextNode = new TrieNode(nextPrefix);
                this.children.put(nextCharacter, nextNode);
            }
            numCharacters++;

            this.children.get(nextCharacter).addChild(numCharacters,value);
        }

    }


    public void reduce(){

        for(ConcurrentHashMap.Entry&lt;String,TrieNode&gt; child : this.children.entrySet()){

            child.getValue().reduce();


            //Get rid of original child mapping
            //this.children.remove(child.getKey());

            //Replace with a new mapping which may include multiple characters if my child has been combined with other children
            String newMapping = child.getValue().getValue().substring(this.getValue().length());

            // only if the new mapping is not equal.
            if (!newMapping.equals(child.getKey())) {
                this.children.remove(child.getKey());
                this.children.put(newMapping, child.getValue());
            }
            //this.children.put(newMapping, child.getValue());

        }

        if(this.children.size() == 1){

            for(ConcurrentHashMap.Entry&lt;String,TrieNode&gt; child : this.children.entrySet()){

                //If I only have a single child, replace it with his children if I&#39;m not also a word on my own
                if(!this.isWord()){

                    //Get rid of the extra child node
                    this.children.remove(child.getKey());

                    //Take the child nodes value, word status and children
                    this.setValue(child.getValue().getValue());
                    this.setIsWord(child.getValue().isWord());
                    for(ConcurrentHashMap.Entry&lt;String,TrieNode&gt; grandchild : child.getValue().getChildrenMappings().entrySet()){
                        this.children.put(grandchild.getKey(),grandchild.getValue());
                    }

                }
            }

        }

    }

    public boolean isWord()
    {
        return this.isWord;
    }

    public void setIsWord(boolean isWord){
        this.isWord = isWord;
    }

    public String getValue()
    {
        return this.value;
    }

    public void setValue(String newValue){
        this.value = newValue;
    }

    public static void main(String[] args){


        TrieNode tN = new TrieNode(&quot;&quot;);


        tN.addChild(0, &quot;www.corriere.it/27esimaora/laquila&quot;);
        tN.addChild(0, &quot;www.corriere.it/27esimaora&quot;);
        tN.addChild(0, &quot;www.corriere.it/cronache/sesso-e-amore/&quot;);
        tN.addChild(0, &quot;www.corriere.it/foto-gallery/cronache/sesso-e-amore/&quot;);

        tN.reduce();

        System.out.println(&quot; root &quot; + tN.getValue());
        System.out.println(&quot; first level child 1 &quot; + tN.getChildren().get(0).getValue());
        System.out.println(&quot; first leve child 2 &quot; + tN.getChildren().get(1).getValue());
        System.out.println(&quot; second level child 1 &quot; + tN.getChildren().get(1).getChildren().get(0).getValue());
        System.out.println(&quot; first  level child 3 &quot; + tN.getChildren().get(2).getValue());

        /*ConcurrentHashMap&lt;String, TrieNode&gt; childrenMappings = tN.getChildren().get(0).getChildren().get(0).getChildren().get(0).getChildrenMappings();


        for(Map.Entry&lt;String, TrieNode&gt; children : childrenMappings.entrySet()){

            System.out.println(children.getKey() + &quot; = &quot; + children.getValue().getChildrenMappings() + children.getValue().getValue() + &quot; &quot;+ children.getValue().isWord);


        }

        System.out.println(tN.getChildren());
        */
    }
}

huangapple
  • 本文由 发表于 2020年4月5日 00:21:40
  • 转载请务必保留本文链接：https://java.coder-hub.com/61031106.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定