Read Text and Search Suffix Array with GUI

Read Text and Search Suffix Array with GUI

Write a java GUI program to build a suffix array for a given text. Your program should be able to read a given text file by the user, build the suffix arrays and search for a pattern. Your program should return the positions (locations) of all occurrences of the given pattern. The program should not exit the searching mode until the user wants to. Therefore, the user may search for more than one pattern on each run of the program.

Solution

SuffixArraySearchApp.java

importjava.io.File;

importjava.io.FileReader;

importjava.io.IOException;

importjava.util.ArrayList;

importjava.util.Arrays;

importjava.util.Collections;

importjavax.swing.JFileChooser;

importjavax.swing.JOptionPane;

importjavax.swing.JTextArea;

/*

* To change this license header, choose License Headers in Project Properties.

* To change this template file, choose Tools | Templates

* and open the template in the editor.

*/

/**

*

*/

public class SuffixArraySearchApp extends javax.swing.JFrame {

/**

* Creates new form SuffixArraySearchApp

*/

publicSuffixArraySearchApp() {

initComponents();

}

/**

* This method is called from within the constructor to initialize the form.

* WARNING: Do NOT modify this code. The content of this method is always

* regenerated by the Form Editor.

*/

@SuppressWarnings(“unchecked”)

// <editor-fold defaultstate=”collapsed” desc=”Generated Code”>//GEN-BEGIN:initComponents

private void initComponents() {

jButton1 = new javax.swing.JButton();

jScrollPane1 = new javax.swing.JScrollPane();

jFileContentArea = new javax.swing.JTextArea();

jButton2 = new javax.swing.JButton();

jPatternField = new javax.swing.JTextField();

jScrollPane3 = new javax.swing.JScrollPane();

jOriginalSuffixArea = new javax.swing.JTextArea();

jScrollPane2 = new javax.swing.JScrollPane();

jSortedSuffixArea = new javax.swing.JTextArea();

jScrollPane4 = new javax.swing.JScrollPane();

jResultArea = new javax.swing.JTextArea();

jLabel1 = new javax.swing.JLabel();

jLabel2 = new javax.swing.JLabel();

jLabel3 = new javax.swing.JLabel();

setDefaultCloseOperation(javax.swing.WindowConstants.EXIT_ON_CLOSE);

setResizable(false);

jButton1.setText(“Select a File”);

jButton1.addActionListener(new java.awt.event.ActionListener() {

public void actionPerformed(java.awt.event.ActionEventevt) {

jButton1ActionPerformed(evt);

}

});

jFileContentArea.setEditable(false);

jFileContentArea.setColumns(20);

jFileContentArea.setRows(5);

jScrollPane1.setViewportView(jFileContentArea);

jButton2.setText(“Search”);

jButton2.addActionListener(new java.awt.event.ActionListener() {

public void actionPerformed(java.awt.event.ActionEventevt) {

jButton2ActionPerformed(evt);

}

});

jScrollPane3.setBounds(new java.awt.Rectangle(-32744, -32569, 320, 100));

jOriginalSuffixArea.setEditable(false);

jOriginalSuffixArea.setColumns(20);

jOriginalSuffixArea.setRows(5);

jOriginalSuffixArea.setBounds(new java.awt.Rectangle(0, 0, 320, 80));

jScrollPane3.setViewportView(jOriginalSuffixArea);

jSortedSuffixArea.setEditable(false);

jSortedSuffixArea.setColumns(20);

jSortedSuffixArea.setRows(5);

jScrollPane2.setViewportView(jSortedSuffixArea);

jResultArea.setEditable(false);

jResultArea.setColumns(20);

jResultArea.setRows(5);

jResultArea.setPreferredSize(new java.awt.Dimension(100, 80));

jResultArea.setSize(new java.awt.Dimension(5, 80));

jScrollPane4.setViewportView(jResultArea);

jLabel1.setText(“List of Suffix”);

jLabel2.setText(“Suffix Array”);

jLabel3.setText(“Index”);

javax.swing.GroupLayout layout = new javax.swing.GroupLayout(getContentPane());

getContentPane().setLayout(layout);

layout.setHorizontalGroup(

layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)

.addGroup(layout.createSequentialGroup()

.addContainerGap()

.addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)

.addGroup(layout.createSequentialGroup()

.addComponent(jScrollPane3)

.addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)

.addComponent(jScrollPane2, javax.swing.GroupLayout.PREFERRED_SIZE, 351, javax.swing.GroupLayout.PREFERRED_SIZE)

.addGap(18, 18, 18)

.addComponent(jScrollPane4, javax.swing.GroupLayout.PREFERRED_SIZE, 99, javax.swing.GroupLayout.PREFERRED_SIZE))

.addGroup(layout.createSequentialGroup()

.addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)

.addGroup(layout.createSequentialGroup()

.addComponent(jButton1)

.addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)

.addComponent(jScrollPane1, javax.swing.GroupLayout.PREFERRED_SIZE, 432, javax.swing.GroupLayout.PREFERRED_SIZE)

.addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.UNRELATED)                                .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)

.addComponent(jButton2)

.addComponent(jPatternField, javax.swing.GroupLayout.PREFERRED_SIZE, 273, javax.swing.GroupLayout.PREFERRED_SIZE)))

.addGroup(layout.createSequentialGroup()

.addComponent(jLabel1)

.addGap(292, 292, 292)

.addComponent(jLabel2)

.addGap(295, 295, 295)

.addComponent(jLabel3)))

.addGap(0, 0, Short.MAX_VALUE)))

.addContainerGap())

);

layout.setVerticalGroup(

layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)

.addGroup(layout.createSequentialGroup()

.addContainerGap()

.addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)

.addGroup(layout.createSequentialGroup()                        .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)

.addComponent(jButton1)

.addComponent(jButton2))

.addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)

.addComponent(jPatternField, javax.swing.GroupLayout.PREFERRED_SIZE, javax.swing.GroupLayout.DEFAULT_SIZE, javax.swing.GroupLayout.PREFERRED_SIZE))

.addComponent(jScrollPane1, javax.swing.GroupLayout.PREFERRED_SIZE, 165, javax.swing.GroupLayout.PREFERRED_SIZE))                .addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)                .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE)

.addComponent(jLabel1)

.addComponent(jLabel2)

.addComponent(jLabel3))

.addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)                .addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)

.addComponent(jScrollPane3, javax.swing.GroupLayout.DEFAULT_SIZE, 380, Short.MAX_VALUE)

.addComponent(jScrollPane2)

.addComponent(jScrollPane4))

.addContainerGap())

);

pack();

}// </editor-fold>//GEN-END:initComponents

// the content of the current file and the suffix array built for it.

// by default, the content is empty and loaded when the user selects a file.

private String content = “”;

private Integer[] sufarr = new Integer[0];

private void jButton1ActionPerformed(java.awt.event.ActionEventevt) {//GEN-FIRST:event_jButton1ActionPerformed

// TODO add your handling code here:

finalJFileChooser fc = new JFileChooser();

// choose a file

fc.setFileSelectionMode(JFileChooser.FILES_ONLY);

finalintretval = fc.showOpenDialog(this);

if (retval != JFileChooser.APPROVE_OPTION) {

return;

}

// load the content of the file to the GUI

final File file = fc.getSelectedFile();

try {

finalFileReader reader = new FileReader(file);

final char[] buf = new char[1024];

finalStringBuilder builder = new StringBuilder();

// read until the end of the file

// and append the content of the file into string builder

intlen;

while ((len = reader.read(buf, 0, buf.length)) >= 0) {

builder.append(buf, 0, len);

}

reader.close();

// put the content to the text area and build up the suffix

// array for the content.

this.content = builder.toString();

this.jFileContentArea.setText(this.content);

// build the suffix and

this.buildSuffixArray();

this.jResultArea.setText(“”);

} catch (final IOException e) {

JOptionPane.showMessageDialog(this, “could not open file ” + file.getPath());

}

}//GEN-LAST:event_jButton1ActionPerformed

private void jButton2ActionPerformed(java.awt.event.ActionEventevt) {//GEN-FIRST:event_jButton2ActionPerformed

// TODO add your handling code here:

this.jResultArea.setText(“”);

final String pattern = this.jPatternField.getText();

if (pattern.length() == 0) { // do nothing, when no pattern is entered.

return;

}

// search the text using suffix tree

// and put the returned indices into the result area

finalArrayList<Integer> indices = search(pattern);

for (int index : indices) {

// the index in the GUI starts with 1 for the first character in the file content.

this.jResultArea.append(index + “\n”);

}

}//GEN-LAST:event_jButton2ActionPerformed

private void displaySuffix(final Integer[] array, final JTextArea area) {

// display the array to the area

area.setText(“”);

for (int index : array) {

String content = String.format(“%2d %s$\n”, index, this.content.substring(index));

area.append(content);

}

}

private void buildSuffixArray() {

// initialize the suffix array to 0 to n

final String value = this.content;

this.sufarr = new Integer[value.length() + 1];

final Integer[] arr = this.sufarr;

for (int i = 0; i <arr.length; i++) {

arr[i] = i;

}

// display the original suffix to the GUI

displaySuffix(arr, jOriginalSuffixArea);

// sort the index array so that the corresponding suffices

// are put in the alphabetically order.

Arrays.sort(arr, new SuffixIndexComparator(value));

// display the sorted suffix array to the GUI

displaySuffix(this.sufarr, jSortedSuffixArea);

}

privateArrayList<Integer> search(final String pattern) {

// binary search in the suffix array

finalArrayList<Integer> result = new ArrayList<>();

int left = 0, right = this.sufarr.length;

while (left < right) {

// compare the pattern with the index in the center of current range in

// the suffix array

finalint middle = left + (right – left) / 2;

finalint diff = compare(this.sufarr[middle], pattern);

if (diff < 0) {

left = middle + 1;

} else if (diff > 0) {

right = middle;

} else {

// we find the location that has suffix matches pattern

// explore in both direction.

result.add(this.sufarr[middle]);

for (int i = middle – 1; i >= 0; i–) { // explore on the left

if (compare(this.sufarr[i], pattern) < 0) {

break;

}

result.add(this.sufarr[i]);

}

for (int i = middle + 1; i <this.sufarr.length; i++) { // explore on the right

if (compare(this.sufarr[i], pattern) > 0) {

break;

}

result.add(this.sufarr[i]);

}

Collections.sort(result);

break;

}

}

return result;

}

privateint compare(final int index, final String pattern) {

// compare the suffix at the given index with the pattern.

// this is used in the binary search from the suffix array.

for (int i = 0; i <pattern.length(); i ++) {

if (index + i >= this.content.length()) {

return -1;

}

finalint diff = this.content.charAt(index + i) – pattern.charAt(i);

if (diff != 0) {

return diff;

}

}

return 0;

}

/**

* @paramargs the command line arguments

*/

public static void main(String args[]) {

/* Set the Nimbus look and feel */

//<editor-fold defaultstate=”collapsed” desc=” Look and feel setting code (optional) “>

/* If Nimbus (introduced in Java SE 6) is not available, stay with the default look and feel.

* For details see http://download.oracle.com/javase/tutorial/uiswing/lookandfeel/plaf.html

*/

try {

for (javax.swing.UIManager.LookAndFeelInfo info : javax.swing.UIManager.getInstalledLookAndFeels()) {

if (“Nimbus”.equals(info.getName())) {

javax.swing.UIManager.setLookAndFeel(info.getClassName());

break;

}

}

} catch (ClassNotFoundException ex) {

java.util.logging.Logger.getLogger(SuffixArraySearchApp.class.getName()).log(java.util.logging.Level.SEVERE, null, ex);

} catch (InstantiationException ex) {

java.util.logging.Logger.getLogger(SuffixArraySearchApp.class.getName()).log(java.util.logging.Level.SEVERE, null, ex);

} catch (IllegalAccessException ex) {

java.util.logging.Logger.getLogger(SuffixArraySearchApp.class.getName()).log(java.util.logging.Level.SEVERE, null, ex);

} catch (javax.swing.UnsupportedLookAndFeelException ex) {

java.util.logging.Logger.getLogger(SuffixArraySearchApp.class.getName()).log(java.util.logging.Level.SEVERE, null, ex);

}

//</editor-fold>

/* Create and display the form */

java.awt.EventQueue.invokeLater(new Runnable() {

public void run() {

newSuffixArraySearchApp().setVisible(true);

}

});

}

// Variables declaration – do not modify//GEN-BEGIN:variables

privatejavax.swing.JButton jButton1;

privatejavax.swing.JButton jButton2;

privatejavax.swing.JTextAreajFileContentArea;

privatejavax.swing.JLabel jLabel1;

privatejavax.swing.JLabel jLabel2;

privatejavax.swing.JLabel jLabel3;

privatejavax.swing.JTextAreajOriginalSuffixArea;

privatejavax.swing.JTextFieldjPatternField;

privatejavax.swing.JTextAreajResultArea;

privatejavax.swing.JScrollPane jScrollPane1;

privatejavax.swing.JScrollPane jScrollPane2;

privatejavax.swing.JScrollPane jScrollPane3;

privatejavax.swing.JScrollPane jScrollPane4;

privatejavax.swing.JTextAreajSortedSuffixArea;

// End of variables declaration//GEN-END:variables

} 

SuffixIndexComparator.java

importjava.util.Comparator;

/*

* To change this license header, choose License Headers in Project Properties.

* To change this template file, choose Tools | Templates

* and open the template in the editor.

*/

/**

* Use to sort the suffix array.

*/

public class SuffixIndexComparator implements Comparator<Integer> {

private final String value;

publicSuffixIndexComparator(final String value) {

this.value = value;

}

@Override

publicint compare(final Integer x, final Integer y) {

// compare the suffix starting at index x and y in the given string value.

finalintlen = this.value.length();

for (int i = 0; ;i ++) {

if (x + i >= len) {

return (y + i >= len) ? 0 : -1;

}

if (y + i >= len) {

return 1;

}

// compare the characters at the current locations

finalint diff = this.value.charAt(x + i) – this.value.charAt(y + i);

if (diff != 0) {

return diff;

}

}

}

}