Results 1 to 6 of 6
Like Tree2Likes
  • 1 Post By Diargg
  • 1 Post By DarrylBurke

Thread: Help to solve text error correction problem using deformed fuzzy automata.

  1. #1
    Join Date
    May 2012
    Posts
    1
    Rep Power
    0

    Post Help to solve text error correction problem using deformed fuzzy automata.

    Hello
    I am facing problem to code my project. It is used to solve the text error correction problem
    Some part of the coding is done but it is not perfect and generates erroneous results.
    The project is based on the deformed fuzzy automata system.

    Base paper on which the code is formulated is attached as pdf. The implemented algorithm is in section 5(newPaper).

    contains the main implementation code of the algorithm is:
    /**
    * DeformedFA.java: This class implements the algorithm
    * that computes the deformed fuzzy automata using the
    * leftmost-child right-sibling representation of the prefix tree.
    * @author Santosh Pattar
    */

    import java.io.IOException;

    import trie.Trie;
    import trie.Trie.Node;

    public class DeformedFA
    {
    private Trie t;

    /**
    * Threshold for states.
    */
    private float tStates;

    /**
    * Threshold for symbols.
    */
    private int tSymbols;

    /**
    * Membership values for edit operations.
    */
    private double mInsert;
    private double mDelete;
    private double mSubstitute;

    /**
    * Similarity value of observed string to the pattern string.
    */
    private double c;

    /**
    * Delete and substitute operation values.
    */
    private double c1;
    private double c2;

    /**
    * Suggested output word for the imperfect string.
    */
    public String match;

    DeformedFA()
    {
    try
    {
    t= new Trie("src/Dictionary.txt");
    }
    catch (IOException e)
    {
    e.printStackTrace();
    }
    finally
    {
    /**
    * Initialize the threshold values.
    */
    tStates=0;
    tSymbols=13; //half the number of alphabets.

    mInsert=0.001;
    mDelete=0.0001;
    mSubstitute=0.0005;
    }

    }

    /**
    * This is the main method of the algorithm.
    * Initializes trie and takes a decision on the
    * similarity measure.
    * @param input word for GUI.
    */
    public String treeComputation(String input)
    {
    treeInitialstate();
    for( int k=1; k<=input.length(); k++ ) //"k" represents a state in deformed fuzzy automata
    {
    rTransition( t.root, 0, k );
    rClosure( t.root.next, t.root.val );
    }
    treeDecision();

    return match;
    }

    /**
    * Traverses a LC-RS tree
    * setting the membership value of root node to 1.
    */
    private void treeInitialstate()
    {
    t.root.val = 1;
    rInitiation( t.root.next );
    rClosure( t.root.next, t.root.val );

    }

    /**
    * Traverses a LC-RS tree recursively
    * setting the membership value of every
    * node except root to 0.
    * @param Subtree of the LC-RS tree.
    */
    private void rInitiation(Node n)
    {
    if(n.letter != null)
    {
    n.val=0;
    rInitiation( n.next );
    rInitiation( n.sibling);
    }
    }

    /**
    * Computes e-closure of a fuzzy state.
    * @param Node of LC-RS tree i.e a fuzzy state.
    * @param Membership value of the fuzzy state.
    */
    private void rClosure(Node n, double v)
    {
    if(n.letter != null)
    {
    n.val = max( n.val, aProduct( v, mInsert ) );

    rClosure( n.next, n.val );
    rClosure( n.sibling, v );
    }

    }

    /**
    * Traverses tree in postorder,
    * for every fuzzy symbol of the observed string.
    * computes membership value of delete and
    * substitute operation respectively.
    * @param Subtree of LC-RS tree.
    * @param Membership value of root node of subtree.
    * @param kth fuzzy state.
    */
    private void rTransition(Node n, double v, int k)
    {
    if( n.letter != null)
    {
    rTransition( n.next, n.val, k);
    rTransition( n.sibling, v, k);

    if( n.val > tStates)
    c1 = aProduct( n.val, tConorm( mDelete ) );
    else
    c1 = 0;

    if( v > tStates )
    c2 = aProduct( v, tConorm( mSubstitute ));
    else
    c2 = 0;

    n.val = max( c1, c2);

    }
    }

    /**
    * Traverses the tree to find a
    * match for the observed string.
    */
    private void treeDecision()
    {
    c = 0;
    match = null;
    rDecision( t.root );
    }

    /**
    * Traverses a tree recursively to
    * find the highest membership values.
    * @param Subtree of LC-RS tree.
    */
    private void rDecision(Node n)
    {
    if( n.letter !=null )
    {
    rDecision( n.next );
    rDecision( n.sibling );

    if( n.isAWord )
    {
    if( n.val > c )
    {
    c = n.val;
    match = match + n.letter;
    }
    }
    }
    }

    /**
    * T-norm operator
    * implemented as algebraic product.
    */
    private double aProduct(double a, double b)
    {
    return a * b;
    }


    /**
    * T-conorm operator.
    * Finds the maximum value among the fuzzy symbols set
    * within the specified symbol threshold "tSymbols".
    * @param Edit operation subjected.
    */
    private double tConorm(double m)
    {
    double[] temp = new double[ tSymbols ];
    double big;

    for ( int i=1; i <= tSymbols; i++)
    {
    temp[i] = aProduct( m, t.listSymbols[i] );
    }

    big = temp[1];
    for( int j=2; j <= tSymbols; j++)
    {
    if( temp[j] > big)
    {
    big = temp[j];
    }

    }

    return big;
    }

    private double max(double a, double b)
    {
    return (a > b) ? a : b ;
    }

    public static void main(String[] args)
    {
    DeformedFA f = new DeformedFA();

    //suggestion for misspelled "youh"
    System.out.println(f.treeComputation("youh"));
    }

    }

    the prefix tree data structure used is found in trie.java :

    /**
    * Trie.java: This class implements a trie.
    */

    /**
    * Description: This program implements a trie that allows to search words. It
    * reads words from a file specified by the user in the command line
    * and constructs the dictionary. It allows user to find, print, add,
    * and delete words from the trie. It folds all inpput into lower-case
    * before storing them or looking them up. It also ignores characters
    * that are not letters and only stores words that are three letters
    * long. A reference pointer is used, when finding a word, the reference
    * pointer will point to this word, when printing it will point to the
    * last printed word, and when deleting it will be reset to the trie root.
    *
    * This class implements a dictionary tree in a structure called trie.
    * We use a representation called "Leftmost-Child-Right-Sibling"
    * representation. A node points to a list of its children and it points
    * to the leftmost child in the list, and each child in the list points
    * to the sibling to the right of it. We add one extra node at the end
    * of the list to implement a pointer back to the parent, using the child
    * pointer in that extra node. The root does not represent any letter, and
    * the last sibling on each list (that points to the parent) has a right
    * sibling pointer set to null.
    *
    * There is a pointer to the current position in the trie, this position
    * is updated when we search a word to point to the start of the found
    * word, when printing it points to the starting position of last printed
    * word, and when deleting it resets position reference to the root. Finding
    * and adding work in the same way, checking first if child node match letter
    * if not then checking with siblings, until a match is found. Printing starts
    * from the starting node position of the word, it goes to the end of the sibling
    * list and then up to the parent node, gets its letter and continues until it
    * get to the root. Deleting starts also from the node starting position of the
    * word and continuous up the tree in the same as printing, but checking on its
    * way if the nodes are still useful, if not it removes reference to these nodes.
    * The basic structure of the trie is a node that contains a specific letter of a
    * word, a child pointer, a sibling pointer and a boolean vallue indicating if
    * this is the starting position of a word. The construction of the trie is done
    * by reading the input file one line at a time and using the add word method.
    *
    * Input: It receives as input in the command line the name of the filename to
    * be used as input in constructing the trie.
    * Later it receives input telling what operation to perform: add, delete
    * or find a word, or print n number of words
    * Output: It prints out wether the operation requested by the user was succesful
    * or not, and the output requested by each command.
    *
    * Status: This class works according to program specifications
    */

    package trie;

    import java.io.*; // For console input

    public class Trie
    {
    public Node root; // Trie root
    public Node current; // Current Position Inside the Trie

    /** Array of letters that are used in comparison operations in order to
    * know which letter is currently being stored into the trie */
    private String[] letters = {"a", "b", "c", "d", "e", "f", "g", "h", "i",
    "j", "k", "l", "m", "n", "o", "p", "q", "r",
    "s", "t", "u", "v", "w", "x", "y", "z"};

    /** Stores the ocurrence of each letter read into the trie, the counter
    * stored at each index corresponds to the letter stored at the same index
    * in array letters */
    private double[] letterCount = new double[26];

    /** Stores the percentage of ocurrence of each letter in the trie, the
    * precentage stored at each index corresponds to the letter stored at the
    * same index in array letters */
    private double[] percentageOfLetter = new double[26];

    // Total number of letters read into the trie
    private double totalLetterCount;

    //Total number of words in the trie
    private int wordCnt;

    /**
    * Sorted list of letters according to the percentage of its occurrence.
    * Value stored at each index is the membership value of corresponding
    * letter stored at the same index in array letters.
    */
    public double[] listSymbols;


    /**
    * Declares an empty trie
    */
    public Trie()
    {
    Node root = new Node();
    }

    /**
    * Build the dictionary trie reading the input from a given filename
    * @param An array of strings with the command line arguments
    * @return None
    */
    public Trie(String commandLine) throws IOException {

    root = new Node(); // Declare a new trie
    BufferedReader reader; // To read from a file
    String input; // Store line of input

    // Check if filename was declared and if it exists
    checkIfValidFilename( commandLine );

    // Declare in which file the input is in
    reader = new BufferedReader( new FileReader ( commandLine ) );

    // Declare in which file the input is in
    //reader = new BufferedReader( new FileReader ( "words" ) );

    // Read each line of the input file
    while ( (input = reader.readLine() ) != null) {

    // Add word to trie
    addWord(input);
    }

    // current position in trie is the root
    current = root;

    // Calculate percentage of ocurrence of letters
    calculatePercentages();
    }

    /**
    * Description: Node
    * This class implement a node structure which is used as the
    * structural components of the trie
    */
    public class Node
    {
    public String letter; // Letter hold in the node
    public boolean isAWord; // Indicates wether this node represents starting positionof a word
    public Node next; // Leftmost child pointer
    public Node sibling; // Right sibling pointer
    public double val; // Membership value of the letter

    /**
    * Creates a new node
    * @param None
    * @return None
    */
    Node ()
    {
    letter = null;
    isAWord = false;
    next = sibling = null;
    val=0;
    }

    /**
    * Creates a new node with given letter and boolean value
    * @param A string for the letter hold in node
    * A boolean value to check if this the start of a word
    * @return None
    */
    Node (String s)
    {
    letter = s;
    isAWord = false;
    next = sibling = null;
    val=0;
    }
    }

    public Boolean isEntry(String word)
    {
    Node pointer = root; // Initialize pointer for position refernce in trie
    String input = word; // Word to look up

    // Start a while loop searching the chars of the word in trie starting backwards
    while (input.length() >= 1)
    {

    // Get the last letter in the word
    String firstChar = input.substring( 0, 1 );
    input = input.substring( 1, input.length() ); // Update string minus last letter

    if ( !Character.isLetter(firstChar.charAt(0)) )
    {
    // If char is not a letter skip it
    continue;
    }

    // Word is not in tree if still looking for word letters and there aren't any more
    if (pointer.next == null)
    {
    return false;
    }
    else
    { // There is a child from the current node

    // Check if next node contains the current letter we're looking for
    if ( pointer.next.letter.equals(firstChar) )
    {
    pointer = pointer.next; // go to next child
    }
    else
    { // Check if a sibling contains the same letter
    pointer = pointer.next; // go to start of node sibling list

    // Loop until a node with the same letter is found or sibling list ends
    while ( pointer.sibling.sibling != null && !pointer.sibling.letter.equals(firstChar) )
    {
    pointer = pointer.sibling;
    }

    // If no sibling with same letter is found, word isn't in trie
    if ( pointer.sibling.sibling == null )
    {
    return false; // String is not in tree
    }
    else
    { // A sibling has the letter we're looking for, continue
    pointer = pointer.sibling; // One sibling has same letter
    }
    }
    }
    }
    // All letters from word match, check if current pointer reference is start of word
    if ( pointer.isAWord == true)
    {
    current = pointer;
    return true; // Return pointer to start of found word
    }
    else
    { // Letters matched, but it not a word in the tree
    return false; // String is not in tree
    }
    }


    /**
    * Add a word to the trie
    * @param The root of the trie
    * The string to be added
    * @return None
    */
    public Node addWord(String input) {
    Node pointer = root;

    // Remove characters that are not letters
    input = removeNonLetterChars(input);

    input = input.toLowerCase(); // Convert string to lower case

    while (input.length() >= 1) {

    // Get the first letter of the word
    String firstChar = input.substring( 0, 1 );

    // Update string minus first letter
    input = input.substring( 1, input.length() );

    // If char is not a letter skip it
    if ( !Character.isLetter(firstChar.charAt(0)) ) {
    continue;
    }

    // Keep track of letters read into the trie
    countLetter(firstChar);

    if (pointer.next == null) {
    // No more child nodes, We need to add a new child
    Node newChild = new Node(firstChar);
    // Set child to be new node
    pointer.next = newChild;

    // Create the last sibling in list pointing to parent
    Node lastSibling = new Node();
    lastSibling.sibling = null;
    lastSibling.next = pointer;
    newChild.sibling = lastSibling;

    pointer = newChild; // Update pointer
    }

    else { // There is still children nodes
    if ( pointer.next.letter.equals(firstChar) ) {
    // node has same letter, go to next child
    pointer = pointer.next;
    }
    else { // Child has not the same letter we're looking for
    pointer = pointer.next;

    // Check if there's a sibling with same letter
    while ( pointer.sibling.sibling != null &&
    !pointer.sibling.letter.equals( firstChar ) ) {

    pointer = pointer.sibling;
    }

    // Check if we got tothe last sibling, node matching letter was not found
    if (pointer.sibling.sibling == null) {

    // Add new node at end of sibling list
    Node newSibling = new Node(firstChar);
    newSibling.sibling = pointer.sibling;
    pointer.sibling = newSibling;
    pointer = newSibling;
    }
    else {
    //There is a node matching the letter we're looking for
    // update pointer to this position
    pointer = pointer.sibling;
    }
    }
    }
    }
    if ( pointer == root ) { // All characters in word were not a letter
    return null; // No word will be added
    }
    wordCnt++;
    pointer.isAWord = true;
    return pointer;

    }

    /**
    * Count the number of times aeach letter is read in the trie
    * @ param A string containing the letter to be counted
    * @ return None
    */
    public void countLetter(String letter) {
    String temp; // Temporary string holder

    // Compare letter to array containing alphabet letters
    for (int i = 0; i < letters.length; i++ ) {
    temp = letters[i];

    // If a match is found
    if ( temp.equals( letter ) ) {

    // Increase counter of that particular letter
    letterCount[i]++;

    // Increase counter of total letters read
    totalLetterCount++;
    }
    }
    }

    /**
    * Calculate the percentage of ocurrance of all letters read into trie
    * @param None
    * @return None
    */
    public void calculatePercentages() {

    // Calculate the percentage of occurrence of each letter
    for (int i = 0; i < percentageOfLetter.length; i++) {

    // Math formula: Percentage ox X = times X occurs * 100 / total
    percentageOfLetter[i] = (letterCount[i]) / totalLetterCount;
    }
    }

    public void sortFuzzyList()
    {
    for(int i=0; i <=percentageOfLetter.length; i++ )
    listSymbols[i] = percentageOfLetter[i];

    int n = listSymbols.length;
    for( int pass = 0; pass < n-1; pass++ )
    {
    int min = pass;
    for( int i = pass+1; i < n; i++ )
    if( listSymbols[i] < listSymbols[min] )
    min = i;
    if( min != pass )
    {
    double tmp = listSymbols[min];
    listSymbols[min] = listSymbols[pass];
    listSymbols[pass] = tmp;
    }
    }
    }

    /**
    * Checks if a file was specified by the user in the inputline to use as input to
    * build the trie, and if it was declared, it checks it exists.
    * @param A string array containing the arguments from the command line
    * @return None
    */
    public static void checkIfValidFilename( String commandLine) throws IOException {
    int numberOfArgs = commandLine.length(); // Number of arguments in command line

    // Check if an input file was actually declared
    if ( numberOfArgs < 1 ) {
    System.out.println( " No Input File Declared." );
    System.out.println( " Ending Program . . . \n" );
    System.exit(0); // End program if no file was declared
    }

    try { // Check if the file actually exists
    BufferedReader reader = new BufferedReader( new FileReader ( commandLine ) );
    }
    catch (FileNotFoundException e) {
    System.out.println( " Input Filename Not Found" );
    System.out.println( " Ending Program . . . \n" );
    System.exit(0); // End program if no file was declared
    }
    }

    /**
    * Removes the non letter characters from the received String and returns that string
    * @ param A string
    * @ return A string with the non letter characters removed
    */
    public String removeNonLetterChars(String word) {

    // Temporary string will hold string with no letter chars
    String tempWord = "";

    // Traverse the entire string
    while ( word.length() >=1 ) {

    // Get the first letter of the word
    String firstChar = word.substring(0, 1);

    // Update string minus first letter
    word = word.substring(1, word.length() );

    //Add character to the new word only if it is a letter
    if ( Character.isLetter( firstChar.charAt(0) ) ) {
    tempWord = tempWord + firstChar;
    }
    }

    // Returned string with no letter chars
    return tempWord;

    }

    /**
    * Check if number in a given string is really a number and bigger than zero
    * @param A string containing a numerical value
    * @return A boolean value, true f string is a number and bigger than zero
    * false otherwise
    */
    public boolean isValidNumber(String str) {
    char[]c = str.toCharArray(); // An array of the chrarcter of the string

    // Check that every character is a number
    for ( int i = 0; i < str.length(); i ++ ) {
    if ( !Character.isDigit( c[i] ) ) {
    System.out.println(" Argument Is Not A Number");
    printInvalidCommand();
    return false;
    }
    }

    int number = Integer.parseInt( str );

    // Check if the number is bigger than zero
    if ( number < 1 ) {
    System.out.println(" Number not valid: Smaller than zero");
    printInvalidCommand();
    return false;
    }
    return true;
    }

    /**
    * Print a invalid command message
    * @param None
    * @return None
    */
    public void printInvalidCommand() {
    System.out.println("Not Valid Command. Please Try Again. ");
    }

    }


    Dictionary.txt contains list of words used to build the prefix tree.
    the LCRS representation does not support a prefix sub tree. the algo present in DeformedFA.java uses several recursive methods which need root of a subtree as parameter,but a node of a subtree is passed to overcome this deficiency which does not seem to work.so please try solving this problem

    So, please help me to solve this problem

  2. #2
    Diargg is offline Senior Member
    Join Date
    Feb 2012
    Posts
    117
    Rep Power
    0

    Default Re: Help to solve text error correction problem using deformed fuzzy automata.

    Use code tags. You should also cut down the roughly 700+ lines of code there to at most a hundred or so to make it something we'll actually read.

    which does not seem to work.
    This is not a useful description of the problem. What happens that is not correct? Describe it to us. For all we know it means that your computer grew legs and ran away after executing your code.

    Mandatory "We're not a homework service, if you want us to do your homework go away or ask a better question"
    Tolls likes this.

  3. #3
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,309
    Blog Entries
    7
    Rep Power
    20

    Default Re: Help to solve text error correction problem using deformed fuzzy automata.

    I agree with the previous poster, mainly because the problem is very ill defined (what attachment?)

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  4. #4
    DarrylBurke's Avatar
    DarrylBurke is offline Member
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,188
    Rep Power
    19

    Default Re: Help to solve text error correction problem using deformed fuzzy automata.

    Quote Originally Posted by santoshpattar01 View Post
    Hello
    I am facing problem to code my project. It is used to solve the text error correction problem
    Some part of the coding is done but it is not perfect and generates erroneous results.
    Cristian Velazquez, why have you held on to this code for 7 years before asking on a forum?
    http://logos.cs.uic.edu/340/assignme...Pop2/Trie.java

    db
    Tolls likes this.
    If you're forever cleaning cobwebs, it's time to get rid of the spiders.

  5. #5
    DarrylBurke's Avatar
    DarrylBurke is offline Member
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,188
    Rep Power
    19

    Default Re: Help to solve text error correction problem using deformed fuzzy automata.

    Quote Originally Posted by JosAH View Post
    (what attachment?)
    Probably on a cross post that Google hasn't yet got round to indexing.

    fn
    If you're forever cleaning cobwebs, it's time to get rid of the spiders.

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,309
    Blog Entries
    7
    Rep Power
    20

    Default Re: Help to solve text error correction problem using deformed fuzzy automata.

    Quote Originally Posted by DarrylBurke View Post
    Probably on a cross post that Google hasn't yet got round to indexing.

    fn
    I suspect that this thread is pure plagiarism; if it is, I suggest it to be removed.

    kind regards,

    Kpd
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Homework - UDP Connection with TCP Error Correction
    By GeekWrath in forum New To Java
    Replies: 0
    Last Post: 03-29-2012, 10:37 PM
  2. Cellular Automata Update Problem
    By samanyu in forum New To Java
    Replies: 17
    Last Post: 06-17-2011, 07:21 AM
  3. plz solve this error
    By silversurfer2in in forum AWT / Swing
    Replies: 14
    Last Post: 06-15-2010, 03:30 PM
  4. Replies: 1
    Last Post: 03-17-2008, 12:59 AM
  5. Help mi solve my error
    By Deon in forum New To Java
    Replies: 3
    Last Post: 01-11-2008, 05:26 AM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •