نمایش نتایج 1 تا 17 از 17

نام تاپیک: ایجاد درخت پسوندی

  1. #1
    کاربر تازه وارد
    تاریخ عضویت
    شهریور 1389
    پست
    83
    تشکر کردن
    31
    18 بار تشکر شده در 18 پست

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

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

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

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

  2. #2
    کاربر دائمی آواتار vahid-p
    تاریخ عضویت
    آذر 1391
    محل زندگی
    تهران
    پست
    1,104
    تشکر کردن
    251
    637 بار تشکر شده در 548 پست

    نقل قول: ایجاد درخت پسوندی

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

  3. کاربرانی که به خاطر مطلب مفید vahid-p از وی تشکر کرده‌اند:


  4. #3
    کاربر تازه وارد
    تاریخ عضویت
    شهریور 1389
    پست
    83
    تشکر کردن
    31
    18 بار تشکر شده در 18 پست

    نقل قول: ایجاد درخت پسوندی



    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);






    }




    }



  5. #4
    کاربر تازه وارد
    تاریخ عضویت
    شهریور 1389
    پست
    83
    تشکر کردن
    31
    18 بار تشکر شده در 18 پست

    نقل قول: ایجاد درخت پسوندی

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

  6. #5
    کاربر دائمی آواتار vahid-p
    تاریخ عضویت
    آذر 1391
    محل زندگی
    تهران
    پست
    1,104
    تشکر کردن
    251
    637 بار تشکر شده در 548 پست

    نقل قول: ایجاد درخت پسوندی

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

  7. #6
    کاربر تازه وارد
    تاریخ عضویت
    شهریور 1389
    پست
    83
    تشکر کردن
    31
    18 بار تشکر شده در 18 پست

    نقل قول: ایجاد درخت پسوندی

    سلام من یه کدی پیدا کردم برای ساخت درخت پسوندی ولی دقیقا نمیدونم چه طوری درخت رو تشکیل میده یعنی برخی کد هاشو متوجه نمیشم.البته این انگار داره از آرایه از لیست پیوندی استفاده میکنه ولی وقتی بریک پوینت میذارم و میبینم داره چی کار میکنه انگار فقط میاد یه رشته رو میگیره و از ابتدا ی رشته یکی یکی از کاراکتر های کم میکنه و میذاره توی یه آرایه ....لطفا میشه شما ببینین اینو ؟ مثلا دستوری که که میگه 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);

    }
    }
    }





  8. #7
    کاربر دائمی آواتار vahid-p
    تاریخ عضویت
    آذر 1391
    محل زندگی
    تهران
    پست
    1,104
    تشکر کردن
    251
    637 بار تشکر شده در 548 پست

    نقل قول: ایجاد درخت پسوندی

    تابع 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 شماره سطح است برای اینکه بتونید درخت رو تشکیل بدید و ببینید آیا اون درختی که میخواید هست یا شبیه اش هست یا نه. اگر نه احتمالا کد درستی رو انتخاب نکردید یا من متوجه نشدم چی میخواید که شاید بهتر باشه دو سه تا مثال از ورودی و خروجی مورد نظرتون بزنید شاید واضحتر بشه. من وقت نکردم زیاد بهش فکر کنم.
    آخرین ویرایش به وسیله vahid-p : جمعه 15 تیر 1397 در 16:01 عصر

  9. کاربرانی که به خاطر مطلب مفید vahid-p از وی تشکر کرده‌اند:


  10. #8
    کاربر تازه وارد
    تاریخ عضویت
    شهریور 1389
    پست
    83
    تشکر کردن
    31
    18 بار تشکر شده در 18 پست

    نقل قول: ایجاد درخت پسوندی

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

  11. #9
    کاربر دائمی آواتار vahid-p
    تاریخ عضویت
    آذر 1391
    محل زندگی
    تهران
    پست
    1,104
    تشکر کردن
    251
    637 بار تشکر شده در 548 پست

    نقل قول: ایجاد درخت پسوندی

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

    بعد هم این درخت قراره چه استفاده ای داشته باشه؟ چنین درختی ندیده بودم قبلا. هر چند منظورتون از پسوندی اگر postfix هست در عبارات ریاضی postfix expression داریم ولی یادم نمیاد برای یک رشته معمولی جایی چنین کاری کرده باشم برای همین نمیتونم پیشفرضی رو داشته باشم. تو کامپایلر هم یه چیزایی بود ولی شباهتی به این نداره
    آخرین ویرایش به وسیله vahid-p : جمعه 22 تیر 1397 در 01:59 صبح

  12. #10
    کاربر تازه وارد
    تاریخ عضویت
    شهریور 1389
    پست
    83
    تشکر کردن
    31
    18 بار تشکر شده در 18 پست

    نقل قول: ایجاد درخت پسوندی

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

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

  13. #11
    کاربر تازه وارد
    تاریخ عضویت
    شهریور 1389
    پست
    83
    تشکر کردن
    31
    18 بار تشکر شده در 18 پست

    نقل قول: ایجاد درخت پسوندی

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

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

  14. #12
    کاربر تازه وارد
    تاریخ عضویت
    شهریور 1389
    پست
    83
    تشکر کردن
    31
    18 بار تشکر شده در 18 پست

    نقل قول: ایجاد درخت پسوندی

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

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

  15. #13
    کاربر دائمی آواتار vahid-p
    تاریخ عضویت
    آذر 1391
    محل زندگی
    تهران
    پست
    1,104
    تشکر کردن
    251
    637 بار تشکر شده در 548 پست

    نقل قول: ایجاد درخت پسوندی

    خب یکم قلق داره و از این ویدیو استفاده کردم: 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);
    }
    }
    }
    }
    آخرین ویرایش به وسیله vahid-p : سه شنبه 26 تیر 1397 در 17:39 عصر دلیل: تصحیح کد

  16. کاربرانی که به خاطر مطلب مفید vahid-p از وی تشکر کرده‌اند:


  17. #14
    کاربر تازه وارد
    تاریخ عضویت
    شهریور 1389
    پست
    83
    تشکر کردن
    31
    18 بار تشکر شده در 18 پست

    نقل قول: ایجاد درخت پسوندی

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

  18. #15
    کاربر تازه وارد
    تاریخ عضویت
    شهریور 1389
    پست
    83
    تشکر کردن
    31
    18 بار تشکر شده در 18 پست

    نقل قول: ایجاد درخت پسوندی

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

  19. #16
    کاربر دائمی آواتار vahid-p
    تاریخ عضویت
    آذر 1391
    محل زندگی
    تهران
    پست
    1,104
    تشکر کردن
    251
    637 بار تشکر شده در 548 پست

    نقل قول: ایجاد درخت پسوندی

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

  20. #17
    کاربر جدید
    تاریخ عضویت
    شهریور 1397
    پست
    12
    تشکر کردن
    0
    0 بار تشکر شده در 0 پست

    نقل قول: خرید آنلاین تخته ترد و شطرنج


تاپیک های مشابه

  1. ایجاد درخت هافمن
    نوشته شده توسط mafila در بخش برنامه نویسی در 6 VB
    پاسخ: 9
    آخرین پست: سه شنبه 19 اردیبهشت 1391, 16:12 عصر
  2. ایجاد درخت
    نوشته شده توسط fazel-d در بخش برنامه نویسی با زبان C و ++C
    پاسخ: 0
    آخرین پست: سه شنبه 21 آبان 1387, 18:03 عصر
  3. سوال: ایجاد درخت 4 تایی پر
    نوشته شده توسط fazel-d در بخش C#‎‎
    پاسخ: 1
    آخرین پست: دوشنبه 13 آبان 1387, 14:38 عصر
  4. ایجاد درخت K تایی و پیدا کردن parent های یک Child
    نوشته شده توسط fazel-d در بخش مباحث عمومی دلفی و پاسکال
    پاسخ: 5
    آخرین پست: پنج شنبه 09 آبان 1387, 14:07 عصر
  5. سوال: طرز ایجاد درخت
    نوشته شده توسط f_masoume در بخش C#‎‎
    پاسخ: 1
    آخرین پست: دوشنبه 21 مرداد 1387, 23:42 عصر

قوانین ایجاد تاپیک در تالار

  • شما نمی توانید تاپیک جدید ایجاد کنید
  • شما نمی توانید به تاپیک ها پاسخ دهید
  • شما نمی توانید ضمیمه ارسال کنید
  • شما نمی توانید پاسخ هایتان را ویرایش کنید
  •