后缀树实现问题
suffix tree implementation issue
我正在研究一些后缀树实现,这里是一个参考实现,问题是 "indexes"(参考第 19 行)如何用于 class SuffixTreeNode?我不确定 "indexes" 是否有用,我想我们可能只需要保留所有节点及其子字符值?没有找到太多 "indexes" 的值用于 class SuffixTreeNode.
欢迎指正。任何见解表示赞赏。
public class SuffixTree {
SuffixTreeNode root = new SuffixTreeNode();
public SuffixTree(String s) {
for (int i = 0; i < s.length(); i++) {
String suffix = s.substring(i);
root.insertString(suffix, i);
}
}
public ArrayList<Integer> getIndexes(String s) {
return root.getIndexes(s);
}
}
public class SuffixTreeNode {
HashMap<Character, SuffixTreeNode> children = new
HashMap<Character, SuffixTreeNode>();
char value;
ArrayList<Integer> indexes = new ArrayList<Integer>();
public SuffixTreeNode() { }
public void insertString(String s, int index) {
indexes.add(index);
if (s != null && s.length() > 0) {
value = s.charAt(0);
SuffixTreeNode child = null;
if (children.containsKey(value)) {
child = children.get(value);
} else {
child = new SuffixTreeNode();
children.put(value, child);
}
String remainder = s.substring(1);
child.insertString(remainder, index);
}
}
public ArrayList<Integer> getIndexes(String s) {
if (s == null || s.length() == 0) {
return indexes;
} else {
char first = s.charAt(0);
if (children.containsKey(first)) {
String remainder = s.substring(1);
return children.get(first).getIndexes(remainder);
}
}
return null;
}
}
public class Question {
public static void main(String[] args) {
String testString = “mississippi”;
String[] stringList = {“is”, “sip”, “hi”, “sis”};
SuffixTree tree = new SuffixTree(testString);
for (String s : stringList) {
ArrayList<Integer> list = tree.getIndexes(s);
if (list != null) {
System.out.println(s + “: “ + list.toString());
}
}
}
}
indexes
肯定是您正在查看的后缀树实现所必需的(后缀树有多个版本,其中一些版本比其他版本更优化)。 indexes
变量在将原始字符串 (mississippi) 中存在子字符串 (is, sip, hi, sis) 的索引返回给调用方法方面起着不可或缺的作用。 getIndexes
returns indexes
在其基本情况下,这就是您获取每个子字符串出现列表的方式。见下面的输出
is: [1, 4]
sip: [6]
sis: [3]
我正在研究一些后缀树实现,这里是一个参考实现,问题是 "indexes"(参考第 19 行)如何用于 class SuffixTreeNode?我不确定 "indexes" 是否有用,我想我们可能只需要保留所有节点及其子字符值?没有找到太多 "indexes" 的值用于 class SuffixTreeNode.
欢迎指正。任何见解表示赞赏。
public class SuffixTree {
SuffixTreeNode root = new SuffixTreeNode();
public SuffixTree(String s) {
for (int i = 0; i < s.length(); i++) {
String suffix = s.substring(i);
root.insertString(suffix, i);
}
}
public ArrayList<Integer> getIndexes(String s) {
return root.getIndexes(s);
}
}
public class SuffixTreeNode {
HashMap<Character, SuffixTreeNode> children = new
HashMap<Character, SuffixTreeNode>();
char value;
ArrayList<Integer> indexes = new ArrayList<Integer>();
public SuffixTreeNode() { }
public void insertString(String s, int index) {
indexes.add(index);
if (s != null && s.length() > 0) {
value = s.charAt(0);
SuffixTreeNode child = null;
if (children.containsKey(value)) {
child = children.get(value);
} else {
child = new SuffixTreeNode();
children.put(value, child);
}
String remainder = s.substring(1);
child.insertString(remainder, index);
}
}
public ArrayList<Integer> getIndexes(String s) {
if (s == null || s.length() == 0) {
return indexes;
} else {
char first = s.charAt(0);
if (children.containsKey(first)) {
String remainder = s.substring(1);
return children.get(first).getIndexes(remainder);
}
}
return null;
}
}
public class Question {
public static void main(String[] args) {
String testString = “mississippi”;
String[] stringList = {“is”, “sip”, “hi”, “sis”};
SuffixTree tree = new SuffixTree(testString);
for (String s : stringList) {
ArrayList<Integer> list = tree.getIndexes(s);
if (list != null) {
System.out.println(s + “: “ + list.toString());
}
}
}
}
indexes
肯定是您正在查看的后缀树实现所必需的(后缀树有多个版本,其中一些版本比其他版本更优化)。 indexes
变量在将原始字符串 (mississippi) 中存在子字符串 (is, sip, hi, sis) 的索引返回给调用方法方面起着不可或缺的作用。 getIndexes
returns indexes
在其基本情况下,这就是您获取每个子字符串出现列表的方式。见下面的输出
is: [1, 4]
sip: [6]
sis: [3]