#java #strin& #trie #suffix-tree
#java #строка #сопоставление #дерево суффиксов
Вопрос:
Я столкнулся с проблемой сопоставления дерева суффиксов, я разработал дерево суффиксов с 26-полосным деревом для представления символов в узле плюс значение, связанное с каждым узлом. Значение каждого узла обозначает либо индекс, с которого строка (если это суффикс) начинается в основной строке, либо -1 в противном случае. После этого я пытаюсь заставить операцию сопоставления работать, но, по-видимому, это не так, и я не могу обнаружить ошибки здесь. Для получения дополнительных разъяснений обратитесь ко второму вопросу в этом PDF-файле. Помогите, пожалуйста.
import java.util.*;
class node{
public int val;
public node ptrs[];
node(){
this.val =0;
ptrs = new node[26];
for (node ptr : ptrs) {
ptr = null;
}
}
}
class Tree{
public node root = new node();
int pass =0;
void insert(Strin& s,int indx) {
node trv = root;
for (int i = 0; i < s.len&th(); i ) {
if (trv.ptrs[s.charAt(i) - 'A'] == null) {
trv.ptrs[s.charAt(i) - 'A'] = new node();
if(i==s.len&th()-1){
trv.ptrs[s.charAt(i)-'A'].val = indx;
}else{
trv.ptrs[s.charAt(i)-'A'].val = -1;
}
}
trv = trv.ptrs[s.charAt(i) - 'A'];
}
}
private void visit(node trv){
for(int i =0;i<26;i ){
if(trv.ptrs[i]!=null){
System.out.println(trv.ptrs[i].val ":" ((char)(i 'A')));
visit(trv.ptrs[i]);
}
}
}
void visit(){
this.visit(root);
}
void leaf(node trv){
if(trv.val&&t;=0){
System.out.println(trv.val);
}else{
for(int i=0;i<26;i ){
if(trv.ptrs[i]!=null){
if(trv.ptrs[i].val&&t;=0){
System.out.println(trv.ptrs[i].val);
}else{
leaf(trv.ptrs[i]);
}
}
}
}
}
private void search(node trv,Strin& s,int i){
if(i<=s.len&th()-1){
if(trv.ptrs[s.charAt(i)-'A']!=null){
if(i==s.len&th()-1){
leaf(trv.ptrs[s.charAt(i)-'A']);
}else{
search(trv.ptrs[s.charAt(i)-'A'], s, i 1);
}
}
}
}
void query(Strin& s){
this.search(root, s, 0);
}
}
public class Trie {
public static void main(Strin&[] ar&s) {
Scanner sc = new Scanner(System.in);
Tree t = new Tree();
Strin& txt = sc.next();
int txtLen = txt.len&th();
for(int i =0;i<txtLen;i ){
t.insert(txt.substrin&(i,txtLen),i);
}
int q = sc.nextInt();
while(q--&&t;0){
Strin& m = sc.next();
t.query(m);
}
sc.close();
}
}
Ожидается :
Input:
AATCGGGTTCAATCGGGGT
2
ATCG
GGGT
Output:
1 4 11 15
Мой вывод :
AATCGGGTTCAATCGGGGT
2
ATCG
11
1
GGGT
4
Как вы можете видеть, я не получаю 15 в качестве ответа.
Комментарии:
1. Пожалуйста, не проходите, я действительно старался изо всех сил найти ошибки, но не смог.
Ответ №1:
Я пытаюсь исследовать вашу программу, но ваша программа плохо написана, и, к сожалению, я не могу найти вашу проблему. Я пытаюсь распечатать его с помощью visit , но полезной информации нет.
Но следующее пытается найти шаблон по дереву суффиксов, которое описано при быстром сопоставлении строк с использованием дерева суффиксов. Может быть, полезно:
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import or&.slf4j.Lo&&er;
import or&.slf4j.Lo&&erFactory;
class Node {
private Strin& text;
private List<Node&&t; children;
private int position;
public Node(Strin& word, int position) {
this.text = word;
this.position = position;
this.children = new ArrayList<&&t;();
}
public Strin& &etText() {
return text;
}
public void setText(Strin& text) {
this.text = text;
}
public int &etPosition() {
return position;
}
public void setPosition(int position) {
this.position = position;
}
public List<Node&&t; &etChildren() {
return children;
}
public void setChildren(List<Node&&t; children) {
this.children = children;
}
public Strin& printTree(Strin& depthIndicator) {
Strin& str = "";
Strin& positionStr = position &&t; -1 ? "[" Strin&.valueOf(position) "]" : "";
str = depthIndicator text positionStr "n";
for (int i = 0; i < children.size(); i ) {
str = children.&et(i)
.printTree(depthIndicator "t");
}
return str;
}
@Override
public Strin& toStrin&() {
return printTree("");
}
}
public class SuffixTree {
private static final Lo&&er LOGGER = Lo&&erFactory.&etLo&&er(SuffixTree.class);
private static final Strin& WORD_TERMINATION = "$";
private static final int POSITION_UNDEFINED = -1;
private Node root;
private Strin& fullText;
public SuffixTree(Strin& text) {
root = new Node("", POSITION_UNDEFINED);
for (int i = 0; i < text.len&th(); i ) {
addSuffix(text.substrin&(i) WORD_TERMINATION, i);
}
fullText = text;
}
public List<Strin&&&t; searchText(Strin& pattern) {
LOGGER.info("Searchin& for pattern "{}"", pattern);
List<Strin&&&t; result = new ArrayList<&&t;();
List<Node&&t; nodes = &etAllNodesInTraversePath(pattern, root, false);
if (nodes.size() &&t; 0) {
Node lastNode = nodes.&et(nodes.size() - 1);
if (lastNode != null) {
List<Inte&er&&t; positions = &etPositions(lastNode);
positions = positions.stream()
.sorted()
.collect(Collectors.toList());
positions.forEach(m -&&t; result.add((markPatternInText(m, pattern))));
}
}
return resu<
}
private void addSuffix(Strin& suffix, int position) {
LOGGER.info("&&t;&&t;&&t;&&t;&&t;&&t;&&t;&&t;&&t;&&t;&&t;&&t; Addin& new suffix {}", suffix);
List<Node&&t; nodes = &etAllNodesInTraversePath(suffix, root, true);
if (nodes.size() == 0) {
addChildNode(root, suffix, position);
LOGGER.info("{}", printTree());
} else {
Node lastNode = nodes.remove(nodes.size() - 1);
Strin& newText = suffix;
if (nodes.size() &&t; 0) {
Strin& existin&SuffixUptoLastNode = nodes.stream()
.map(a -&&t; a.&etText())
.reduce("", Strin&::concat);
// Remove prefix from newText already included in parent
newText = newText.substrin&(existin&SuffixUptoLastNode.len&th());
}
extendNode(lastNode, newText, position);
LOGGER.info("{}", printTree());
}
}
private List<Inte&er&&t; &etPositions(Node node) {
List<Inte&er&&t; positions = new ArrayList<&&t;();
if (node.&etText()
.endsWith(WORD_TERMINATION)) {
positions.add(node.&etPosition());
}
for (int i = 0; i < node.&etChildren()
.size(); i ) {
positions.addAll(&etPositions(node.&etChildren()
.&et(i)));
}
return positions;
}
private Strin& markPatternInText(Inte&er startPosition, Strin& pattern) {
Strin& matchin&TextLHS = fullText.substrin&(0, startPosition);
Strin& matchin&Text = fullText.substrin&(startPosition, startPosition pattern.len&th());
Strin& matchin&TextRHS = fullText.substrin&(startPosition pattern.len&th());
return matchin&TextLHS "[" matchin&Text "]" matchin&TextRHS;
}
private void addChildNode(Node parentNode, Strin& text, int position) {
parentNode.&etChildren()
.add(new Node(text, position));
}
private void extendNode(Node node, Strin& newText, int position) {
Strin& currentText = node.&etText();
Strin& commonPrefix = &etLon&estCommonPrefix(currentText, newText);
if (commonPrefix != currentText) {
Strin& parentText = currentText.substrin&(0, commonPrefix.len&th());
Strin& childText = currentText.substrin&(commonPrefix.len&th());
splitNodeToParentAndChild(node, parentText, childText);
}
Strin& remainin&Text = newText.substrin&(commonPrefix.len&th());
addChildNode(node, remainin&Text, position);
}
private void splitNodeToParentAndChild(Node parentNode, Strin& parentNewText, Strin& childNewText) {
Node childNode = new Node(childNewText, parentNode.&etPosition());
if (parentNode.&etChildren()
.size() &&t; 0) {
while (parentNode.&etChildren()
.size() &&t; 0) {
childNode.&etChildren()
.add(parentNode.&etChildren()
.remove(0));
}
}
parentNode.&etChildren()
.add(childNode);
parentNode.setText(parentNewText);
parentNode.setPosition(POSITION_UNDEFINED);
}
private Strin& &etLon&estCommonPrefix(Strin& str1, Strin& str2) {
int compareLen&th = Math.min(str1.len&th(), str2.len&th());
for (int i = 0; i < compareLen&th; i ) {
if (str1.charAt(i) != str2.charAt(i)) {
return str1.substrin&(0, i);
}
}
return str1.substrin&(0, compareLen&th);
}
private List<Node&&t; &etAllNodesInTraversePath(Strin& pattern, Node startNode, boolean isAllowPartialMatch) {
List<Node&&t; nodes = new ArrayList<&&t;();
for (int i = 0; i < startNode.&etChildren()
.size(); i ) {
Node currentNode = startNode.&etChildren()
.&et(i);
Strin& nodeText = currentNode.&etText();
if (pattern.charAt(0) == nodeText.charAt(0)) {
if (isAllowPartialMatch amp;amp; pattern.len&th() <= nodeText.len&th()) {
nodes.add(currentNode);
return nodes;
}
int compareLen&th = Math.min(nodeText.len&th(), pattern.len&th());
for (int j = 1; j < compareLen&th; j ) {
if (pattern.charAt(j) != nodeText.charAt(j)) {
if (isAllowPartialMatch) {
nodes.add(currentNode);
}
return nodes;
}
}
nodes.add(currentNode);
if (pattern.len&th() &&t; compareLen&th) {
List<Node&&t; nodes2 = &etAllNodesInTraversePath(pattern.substrin&(compareLen&th), currentNode, isAllowPartialMatch);
if (nodes2.size() &&t; 0) {
nodes.addAll(nodes2);
} else if (!isAllowPartialMatch) {
nodes.add(null);
}
}
return nodes;
}
}
return nodes;
}
public Strin& printTree() {
return root.printTree("");
}
public static void main(Strin&[] ar&s) {
SuffixTree suffixTree = new SuffixTree("AATCGGGTTCAATCGGGGT");
List<Strin&&&t; matches = suffixTree.searchText("ATCG");
matches.stream().forEach(m -&&t; { System.out.println(m);});
List<Strin&&&t; matches2 = suffixTree.searchText("GGGT");
matches2.stream().forEach(m -&&t; { System.out.println(m);});
}
}
Комментарии:
1. Я не понимаю, на мой взгляд, программу, ну, она написана для решения проблемы типа отправки, и я считаю, что она написана так просто, как ее мог бы написать кто угодно. Я, конечно, не продвинутый пользователь Java, и поэтому ваша программа не очень помогает. Не могли бы вы дать объяснение.
2. @PawanNirpal! не беспокойтесь о своем коде. вы станете экспертом как можно скорее. Полное объяснение приведено в указанном URL в СООБЩЕНИИ. Пожалуйста, прочтите это и сосредоточьтесь на своем коде. Например,
visit()функция вам не поможет. Вы должны иметь возможность распечатать ветвь вашего дерева, чтобы найти, в чем ваша ошибка. Я не могу этого сделать с помощью visit, а в вашей древовидной структуре много нулевых записей.