ایجاد درخت پسوندی

[foroughiiii]

سلام ، من توی جاوا مبتدی هستم و لی برای پروژه ام لازم دارم خودم کد بنویسم میشه راهنماییم کنید؟

من برای نوشتن درخت پسوندی میخوام اینجوری عمل کنم
1. رشته رو ازورودی و بعدش اگه بهتر نوشتم از فایل بخونه.
2.آرایه پسوندی براش تشکیل بدم.
3. از روی آرایه پسوندی درخت پسوندی رو تشکیل بدم.

میشه لطفا خواهشا راهتماییم کنید.مرحله به مرحله. من منتظرم.

[vahid-p]

کدی که تا الان بهش رسیدید رو بذارید تا مشخص بشه کجاش مشکل دارید.
این سوالی که پرسیدید خیلی کلیه و در اصل سوال هم نپرسیدید، در مورد کل این پروژه راهنمایی خواستید که در تاپیک ها به این صورت مطرح نمیشن. به هر حال اگر راهنمایی کلی بخواید، یعنی در مورد هر کدومش باید تدریس بشه، پس من میتونم لینک بدم فقط:
1- https://www.geeksforgeeks.org/scanner-class-in-java
2,3- https://www.geeksforgeeks.org/expression-tree

[foroughiiii]

package mysuffixtree;
//import java.util.Scanner;
import java.io.*;
import java.util.LinkedList;
import java.util.List;






/**
*
* @author 4ough
*/
public class MySuffixTree {


/**
* @param args the command line arguments
*/



public static void main(String[] args) throws IOException {
/*گرفتن یک رشته از ورودی و نوشتن آن در صفحه نمایش*/
// TODO code application logic here
///Scanner st=new Scanner(System.in);
//String name;
//System.out.print("enter your string:");
//name=st.next();
// System.out.print("your name is"+" "+name);

/*خواندن از یک فایل و نوشتن کاراکتر های آن در صفحه نمایش*/



FileInputStream in=null;
in = new FileInputStream("file.txt");
int size;
size=in.available();
System.out.println(" file size is: "+size);
String[] sufixarray= new String[size];
char s;
int j;
int c;
int [] index=new int[size];
for(j=0;j<size;j++)
{
s=(char)in.read();//خواندن کاراکتر ها از فایل و ریختن آن ها در اس
sufixarray[j]=Character.toString(s);//تبدیل کاراکتر به رشته
System.out.println("Character at 0 index is: "+sufixarray[j]);


}
//تشکیل آرایه پسوندی از رشته درون فایل
System.out.println("**********creating suffix array************************");
String text = "";
c=(sufixarray.length)-1;
for(j=(sufixarray.length)-1;j>=0;j--)
{
text=sufixarray[c]+text;
sufixarray[j]=text;
index[j]=j;
c=c-1;
System.out.print(index[j]+":");
System.out.println(sufixarray[j]);
}
// ساختن درخت پسوندی
//ایندکس ها در آرایه ایندکس ذخیره می شوند.
// suffix_tree(a);






}




}

[foroughiiii]

یه فایل ورودی هم داره با پسوند txt که هرچی توش وارد کنیم آرایه پسوندی براش درست میکنه

[vahid-p]

خب این قسمتش که زیاد مهم نیست.
فرض کنید آرایه آماده دارید، suffix_tree رو چیکار کردید؟

[foroughiiii]

سلام من یه کدی پیدا کردم برای ساخت درخت پسوندی ولی دقیقا نمیدونم چه طوری درخت رو تشکیل میده یعنی برخی کد هاشو متوجه نمیشم.البته این انگار داره از آرایه از لیست پیوندی استفاده میکنه ولی وقتی بریک پوینت میذارم و میبینم داره چی کار میکنه انگار فقط میاد یه رشته رو میگیره و از ابتدا ی رشته یکی یکی از کاراکتر های کم میکنه و میذاره توی یه آرایه ....لطفا میشه شما ببینین اینو ؟ مثلا دستوری که که میگه indexes = new LinkedList<Integer>(); v رو متوجه نمیشم از نظر ساختاری. و اینکه چرا هر بار index رو add میکنه با توجه به این که ممکنه تکراری باشه مقادیرش.میشه برام کدشو توضیح بدین شمایی که جاوا تون خوبه؟







package suffix_tree;


import java.io.IOException;
import java.util.LinkedList;
import java.util.List;


/**
*
* @author 4ough
*/
public class Suffix_tree {


SuffixTrieNode root = new SuffixTrieNode();

// Constructor (Builds a trie of suffies of the
// given text)

Suffix_tree(String txt) {

// Consider all suffixes of given string and
// insert them into the Suffix Trie using
// recursive function insertSuffix() in
// SuffixTrieNode class
String p=null;
for (int i = 0; i < txt.length(); i++)
{
p=txt.substring(i);
root.insertSuffix(p,i);
}
}

/**
* @param args the command line arguments
* @throws java.io.IOException
*/
public static void main(String[] args) throws IOException {
String txt = "forough";
new Suffix_tree(txt);
// TODO code application logic here
}

}
class SuffixTrieNode {

final static int MAX_CHAR = 256;

SuffixTrieNode[] children = new SuffixTrieNode[MAX_CHAR];
List<Integer> indexes;

SuffixTrieNode() // Constructor
{
// Create an empty linked list for indexes of
// suffixes starting from this node
indexes = new LinkedList<Integer>();

// Initialize all child pointers as NULL
for (int i = 0; i < MAX_CHAR; i++)
children[i] = null;
}

// A recursive function to insert a suffix of
// the text in subtree rooted with this node
void insertSuffix(String s, int index) {
String c=null;
// Store index in linked list
indexes.add(index);
// If string has more characters
if (s.length() > 0) {

// Find the first character
char cIndex = s.charAt(0);

// If there is no edge for this character,
// add a new edge
if (children[cIndex] == null)
children[cIndex] = new SuffixTrieNode();

// Recur for next suffix
c=s.substring(1);
children[cIndex].insertSuffix(c,index + 1);

}
}
}

[vahid-p]

تابع main رو به این صورت زیر تغییر دادم ولی اینکه ایندکس شماره 7 داریم در صورتی که رشتمون تا ایندکس 6 داره، شاید منظورش یه چیز دیگه بوده.
public static void main(String[] args) throws IOException {
String txt = "forough";
Suffix_tree suf = new Suffix_tree(txt);
printNode(null, suf.root, 0, txt);
}


static void printNode(SuffixTrieNode parent, SuffixTrieNode node, int depth, String chars) {
if (node == null) {
return;
}
if (node.indexes != null) {
if (parent == null || parent.indexes == null) {
System.out.print("[P:" + parent + ", L:" + depth + "] :");
} else {
System.out.print("[P:" );
for (Integer index : parent.indexes) {
if (index < chars.length()) {
System.out.print(chars.charAt(index));
} else {
System.out.print("null");
}
}
System.out.print(", L:" + depth + "] :");
}
for (Integer index : node.indexes) {
if (index < chars.length()) {
System.out.print(chars.charAt(index));
} else {
System.out.print("null");
}
}
System.out.println();
}
System.out.flush();
if (node.children != null) {
for (SuffixTrieNode suf : node.children) {
printNode(node, suf, depth + 1, chars);
}
}
}
خروجی:

[P:null, L:0] :forough
[P:forough, L:1] :o
[P:o, L:2] :r
[P:r, L:3] :o
[P:o, L:4] :u
[P:u, L:5] :g
[P:g, L:6] :h
[P:h, L:7] :null
[P:forough, L:1] :h
[P:h, L:2] :null
[P:forough, L:1] :null
[P:forough, L:1] :ru
[P:ru, L:2] :o
[P:o, L:3] :u
[P:u, L:4] :g
[P:g, L:5] :h
[P:h, L:6] :null
[P:ru, L:2] :g
[P:g, L:3] :h
[P:h, L:4] :null
[P:forough, L:1] :o
[P:o, L:2] :u
[P:u, L:3] :g
[P:g, L:4] :h
[P:h, L:5] :null
[P:forough, L:1] :g
[P:g, L:2] :h
[P:h, L:3] :null

منظور از P یعنی parent و L شماره سطح است برای اینکه بتونید درخت رو تشکیل بدید و ببینید آیا اون درختی که میخواید هست یا شبیه اش هست یا نه. اگر نه احتمالا کد درستی رو انتخاب نکردید یا من متوجه نشدم چی میخواید که شاید بهتر باشه دو سه تا مثال از ورودی و خروجی مورد نظرتون بزنید شاید واضحتر بشه. من وقت نکردم زیاد بهش فکر کنم.

[foroughiiii]

سلام ببخشید من چند وقتی اینترنت نداشتم
ببینین من میخوام یه درخت پسوندی مثل این تصویری که میفرستم باشه.
148529

[vahid-p]

توضیحی رو هم اضافه کنید چطور این درخت تشکیل شده. مثلا کلمه banana رو خواستید این درخت رو براش تشکیل بدید کی یک شاخه ادامه پیدا میکنه کی چند شاخه میشه و...
مثلا درشاخه سمت چپ همه مستقیم رفتن تا به نال رسیده. ولی در بقیه شاخه ها اونایی که از n میره یه مسیر هم به نال میره.

بعد هم این درخت قراره چه استفاده ای داشته باشه؟ چنین درختی ندیده بودم قبلا. هر چند منظورتون از پسوندی اگر postfix هست در عبارات ریاضی postfix expression داریم ولی یادم نمیاد برای یک رشته معمولی جایی چنین کاری کرده باشم برای همین نمیتونم پیشفرضی رو داشته باشم. تو کامپایلر هم یه چیزایی بود ولی شباهتی به این نداره

[foroughiiii]

سلام دوباره
درخت پسوندی هستش

به خاطر اینکه نمیدونم ساختارش چه شکلیه دچار مشکل هستم
اول باید پسوند های banana تشکیل بشه
مثل
banana
anana
nana
ana
na
a
حالا اگه به این درخت نگاه کنین میبینید از ریشه به هر شاخه ای بره این پسوند ها رو شامل میشه
این یه ساختار برای جستجو هستش
من نمیدونم چه طوری این درخت رو تشکیل بدم توی جاوا

[foroughiiii]

به این درخت میگن suffix tree
به اخر رشته یه کاراکتر اضافه میشه که انتهای رشته رو مشخص کنه.

حالا شما میتونین منو راهنمایی کنین چه طوری با لیست پیوندی یا آرایه ای از لیست پیوندی این درخت رو تشکیل بدم؟
و بعدش بسطش بدم به هر رشته ای؟

[foroughiiii]

انگار اول میاد حروف موجود توی رشته رو تشخیص میده ، بعد توی یه حالت بازگشتی از اولین حرف الفبا به ترتیب حروف الفبا شروع میکنه میگه خب هر حرفی طبق پسوند مورد نظر به کدوم حرف دیگه متصله و همین طور به ترتیب ادامه میده تا به کاراکتر اضافی که برای مشخص شدن انتهای پسوند به رشته اضافه شده بود برسه.با رسیدن به کارکتر انتهایی از این شاخه بیرون میاد و میره حرف بعدی

تا بتونه این طوری تمام پسوند های رشته رو تشکیل بده

[vahid-p]

خب یکم قلق داره و از این ویدیو استفاده کردم: https://www.youtube.com/watch?v=VA9m_l6LpwI

طبق این ویدیو کد زیر رو نوشتم که با دو تست banana و CAGTCAGG (مثال ویدیو) خروجی زیر رو میده:


----------- Test1 -----------[P:null,L0]: (-1,null)
[P:root,L1]: (-1,a)
[P:a,L2]: (5,$)
[P:a,L2]: (-1,na)
[P:na,L3]: (3,$)
[P:na,L3]: (1,na$)
[P:root,L1]: (-1,na)
[P:na,L2]: (4,$)
[P:na,L2]: (2,na$)
[P:root,L1]: (0,banana$)
----------- Test2 -----------
[P:null,L0]: (-1,null)
[P:root,L1]: (-1,G)
[P:G,L2]: (7,$)
[P:G,L2]: (6,G$)
[P:G,L2]: (2,TCAGG$)
[P:root,L1]: (-1,AG)
[P:AG,L2]: (5,G$)
[P:AG,L2]: (1,TCAGG$)
[P:root,L1]: (-1,CAG)
[P:CAG,L2]: (4,G$)
[P:CAG,L2]: (0,TCAGG$)
[P:root,L1]: (3,TCAGG$)

که ایندکس ها برخلاف ویدیو از صفر شروع میشه. L هم سطح گره در درخت رو مشخص میکنه و ایندکس -1 هم به معنی نودهای میانی است. (ویرایش/حل شد:با این وجود مثال دوم "L[2]: (-1,)" اشتباهه و بقیش درست به نظر میاد که احتمالا جایی باگ داره و دقت نکردم، همینشم وقت گیر بود یکم.)
مشکل هم به این صورت حل شد که if (this.index == -1) { //non-leaf (including root at start) که قبلا if(this.value==null بود و فقط root رو در نظر میگرفت ولی این حالت برای نودهای میانی که قبلا شاخه شاخه شدن هم وجود داره و باید در نظر گرفت
کد:
package main;

import java.util.ArrayList;
import javafx.util.Pair;


public class SuffixTree {


public static void main(String[] args) {
System.out.println("----------- Test1 -----------");
SuffixTree suffixTree = new SuffixTree("banana");
printNode(null, suffixTree.root, 0);
System.out.println("----------- Test2 -----------");
SuffixTree suffixTree2 = new SuffixTree("CAGTCAGG");
printNode(null, suffixTree2.root, 0);
}


public static void printNode(Node parent, Node node, int depth) {
if (parent != null) {
System.out.println("[P:" + (parent.value==null?"root":parent.value) + ",L:" + depth + "]: (" + node.index + "," + node.value + ")");
} else {
System.out.println("[P:null,L:" + depth + "]: (" + node.index + "," + node.value + ")");
}
for (Node n : node.children) {
printNode(node, n, depth + 1);
}
}


Node root;
String mainString;
ArrayList<Pair<Integer, String>> suffixes;


public SuffixTree(String str) {
if (str.length() < 1) {
return;
}
mainString = str + '$';
//Suffixes List
suffixes = new ArrayList<>();
for (int i = mainString.length() - 2; i >= 0; i--) {
suffixes.add(new Pair<>(i, mainString.substring(i)));
}
//Create Suffix Tree
root = new Node(-1, null);
for (Pair<Integer, String> suffix : suffixes) {
root.insertString(suffix.getKey(), suffix.getValue());
}
}


private class Node {


int index; //-1 means it's a non-leaf node
String value; //Just root value is null
ArrayList<Node> children;


public Node(int index, String value) {
this.index = index;
this.value = value;
this.children = new ArrayList<>();
}


public void insertString(int index, String value) {
int end = 0;
Node found = null;
if (this.value != null) {//non-root
//find shared sub-string
for (end = 0; end < this.value.length(); end++) {
if (this.value.charAt(end) != value.charAt(end)) {
break;
}
}
value = value.substring(end);
}


for (Node node : children) {
if (node.value.charAt(0) == value.charAt(0)) {
found = node;
break;
}
}


if (found == null) {
if (this.index == -1) { //non-leaf (including root at start)
this.children.add(new Node(index, value));
} else { //needs branch
//branch
this.children.add(new Node(this.index, this.value.substring(end)));
this.children.add(new Node(index, value));
this.index = -1;
this.value = this.value.substring(0, end);
}
} else {
found.insertString(index, value);
}
}
}
}

[foroughiiii]

واقعا ممنونم یعنی این الان واسه هر رشته ای کار میکنه؟ میشه اگه بازم سوال داشتم بپرسم؟

[foroughiiii]

الان این کدو خودتون نوشتین؟ چه طوری میتونین اینقدر خوب کد بنویسین؟

[vahid-p]

بله، از توضیحات ویدیو کمک گرفتم و با دیباگ کردن نسخه اولیه ای که نوشتم و بررسی مرحله به مرحله کد سعی کردم بهترش کنم. اگر وقت بذارید میشه.
ضمنا پست قبل رو ویرایش کردم و اون مشکلی بود حل شد. به هر حال بهتره قبل از استفاده از هر کدی با چندین تست کیس امتحان کنید.

[foroughiiii]

من میخوام دو تا رشته به این برنامه بدم و بعد از تشکیل درخت پسوندی برای هرگدوم ، تو یه حلقه به ازای مقدار روی هر یال درخت به تمام ند های موجود در یال های درخت بعدی دسترسی پیدا کنم .میتونین بهم کمک کنین؟
مثلا اگر یادل اول درخت اول Aهستش ، بره تو درخت دوم رشته های موجود در تمام یال هارو برام بیاره.میتونین این کارو بهم کمک کنین که تو کد شما چه طوری این کارو انجام بدم؟

[foroughiiii]

لطفا میشه بهم کمک کنید؟