001/**
002 * Copyright (C) 2007 - 2016, Jens Lehmann
003 *
004 * This file is part of DL-Learner.
005 *
006 * DL-Learner is free software; you can redistribute it and/or modify
007 * it under the terms of the GNU General Public License as published by
008 * the Free Software Foundation; either version 3 of the License, or
009 * (at your option) any later version.
010 *
011 * DL-Learner is distributed in the hope that it will be useful,
012 * but WITHOUT ANY WARRANTY; without even the implied warranty of
013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
014 * GNU General Public License for more details.
015 *
016 * You should have received a copy of the GNU General Public License
017 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
018 */
019package org.dllearner.algorithms.qtl.filters;
020
021import java.util.Collection;
022import java.util.Collections;
023import java.util.HashSet;
024import java.util.Set;
025import java.util.SortedSet;
026import java.util.TreeSet;
027
028import org.dllearner.algorithms.qtl.datastructures.QueryTree;
029import org.dllearner.algorithms.qtl.datastructures.impl.QueryTreeImpl;
030
031import uk.ac.shef.wit.simmetrics.similaritymetrics.AbstractStringMetric;
032import uk.ac.shef.wit.simmetrics.similaritymetrics.Levenshtein;
033import uk.ac.shef.wit.simmetrics.similaritymetrics.QGramsDistance;
034
035public class KeywordBasedQueryTreeFilter implements QueryTreeFilter{
036        
037        private Collection<String> questionWords;
038        
039        private AbstractStringMetric qGramMetric;
040        private AbstractStringMetric levensteinMetric;
041        private I_Sub substringMetric;
042        
043        private double threshold = 0.4;
044        private int topK = 3;
045        private double topKSumThreshold = 0.8;
046        
047        public KeywordBasedQueryTreeFilter(Collection<String> questionWords){
048                this.questionWords = questionWords;
049                qGramMetric = new QGramsDistance();
050                levensteinMetric = new Levenshtein();
051                substringMetric = new I_Sub();
052        }
053        
054        @Override
055        public QueryTree<String> getFilteredQueryTree(QueryTree<String> tree){
056                QueryTree<String> copy = new QueryTreeImpl<>(tree);
057                filterTree(copy);
058                return copy;
059        }
060        
061        public Collection<String> getQuestionWords(){
062                return questionWords;
063        }
064        
065        public void setThreshold(double threshold){
066                this.threshold = threshold;
067        }
068        
069        private void filterTree(QueryTree<String> tree){
070                String edge;
071                for(QueryTree<String> child : tree.getChildren()){
072                        if(child.getUserObject().equals("?")){
073                                edge = (String) tree.getEdge(child);
074                                if(!isSimiliar2QuestionWord(getFragment(edge))){
075                                        child.getParent().removeChild((QueryTreeImpl<String>) child);
076                                }
077                        } else {
078                                filterTree(child);
079                        }
080                }
081        }
082        
083        private boolean isSimiliar2QuestionWord(String s){
084                for(String word : questionWords){
085                        if(areSimiliar(word, s)){
086                                return true;
087                        }
088                } 
089                return isSimlarWithSubstringMetrik(s);
090        }
091        
092        private boolean areSimiliar(String s1, String s2){
093                return (qGramMetric.getSimilarity(s1, s2) >= threshold) || 
094                (levensteinMetric.getSimilarity(s1, s2) >= threshold);
095        }
096        
097        private boolean isSimlarWithSubstringMetrik(String s){
098                SortedSet<Double> values = new TreeSet<>(Collections.reverseOrder());
099                for(String word : questionWords){
100                        double v = substringMetric.score(word, s, true);
101                        if(v >= threshold){
102                                return true;
103                        } else {
104                                values.add(v);
105                        }
106                } 
107                double sum = 0;
108                for(Double v : getTopK(values)){
109                        if(v >= 0){
110                                sum += v;
111                        }
112                        
113                }
114                return sum >= topKSumThreshold;
115        }
116        
117        private Set<Double> getTopK(SortedSet<Double> values){
118                Set<Double> top = new HashSet<>();
119                int k = 0;
120                for(Double v : values){
121                        if(k == topK){
122                                break;
123                        }
124                        top.add(v);
125                        k++;
126                }
127                return top;
128        }
129        
130        private String getFragment(String uri){
131                int i = uri.lastIndexOf("#");
132                if(i > 0){
133                        return uri.substring(i+1);
134                } else {
135                        return uri.substring(uri.lastIndexOf("/")+1);
136                }
137        }
138        
139
140}