Skip to content

Commit ac8fc02

Browse files
nullbitesnullbites
committed
Added String matching tool
Uses the KMP algorithm to efficiently search for characters or Strings in a text
1 parent 8fdca60 commit ac8fc02

1 file changed

Lines changed: 279 additions & 0 deletions

File tree

‎src/DNAStringMatching.java‎

Lines changed: 279 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,279 @@
1+
import java.io.BufferedReader;
2+
import java.io.File;
3+
import java.io.FileNotFoundException;
4+
import java.io.FileReader;
5+
import java.io.IOException;
6+
import java.nio.file.Files;
7+
import java.util.ArrayList;
8+
9+
import javax.swing.JOptionPane;
10+
11+
public class DNAStringMatching {
12+
13+
private File enzimasRestriccion, busqueda;
14+
private String adn;
15+
private ArrayList<String[][]> tablasKMP;
16+
private ArrayList<int[]> tablasKMPIndex;
17+
private ArrayList<String[]> enzimas;
18+
19+
//Recibe los dos archivos
20+
public void ingresaTexto() {
21+
//Pedir path de archivo con enzimas de restricción
22+
String possiblePath = "";
23+
do {
24+
possiblePath = JOptionPane.showInputDialog("Ingresa el path del archivo que contenga las enzimas de restricción a buscar");
25+
if(possiblePath == null) {
26+
System.exit(0);
27+
}
28+
} while(possiblePath.equals(""));
29+
this.enzimasRestriccion = new File(possiblePath);
30+
31+
//Pedir path de archivo con ADN donde se va a buscar
32+
possiblePath = "";
33+
do {
34+
possiblePath = JOptionPane.showInputDialog("Ingresa el path del archivo que contenga el genoma donde se realizará la "
35+
+ "busqueda");
36+
if(possiblePath == null) {
37+
System.exit(0);
38+
}
39+
} while(possiblePath.equals(""));
40+
this.busqueda = new File(possiblePath);
41+
}
42+
43+
//Procesar archivo de busqueda
44+
public void procesarArchivo() {
45+
System.out.println("Path ingresado: " + this.busqueda.getPath());
46+
System.out.println("Eliminando espacios y caracteres basura");
47+
this.adn = convertFile(this.busqueda);
48+
System.out.println("...");
49+
System.out.println("Texto con formato correcto");
50+
System.out.println();
51+
System.out.println();
52+
}
53+
54+
55+
//La entrada es el número de enzima a buscar
56+
public void busquedaGeneral(int seleccion) {
57+
this.buscarEnzima(this.adn, seleccion);
58+
}
59+
60+
//Para buscar una sola enzima
61+
private void buscarEnzima(String adn, int seleccion) {
62+
System.out.println("--------------------Comenzando busqueda--------------------");
63+
System.out.println("Buscando para " + this.enzimas.get(seleccion)[0]);
64+
System.out.println("...");
65+
int coincidencias = this.fuerzaBruta(adn, this.enzimas.get(seleccion)[1], seleccion);
66+
System.out.println("Se encontraron " + coincidencias + " coindidencias de los caracteres " + this.enzimas.get(seleccion)[1]);
67+
System.out.println();
68+
System.out.println("Busqueda finalizada");
69+
System.out.println();
70+
System.out.println();
71+
}
72+
73+
//Para buscar 1 o más enzimas
74+
private void buscarEnzimas(String adn, int seleccion) {
75+
System.out.println("Comenzando busqueda");
76+
System.out.println();
77+
for(int nEnzimas = 0; nEnzimas < this.enzimas.size(); nEnzimas++) {
78+
String[] enzimaActual = this.enzimas.get(nEnzimas);
79+
System.out.println("Buscando para " + enzimaActual[0]);
80+
System.out.println("...");
81+
int coincidencias = this.fuerzaBruta(adn, enzimaActual[1], seleccion);
82+
System.out.println("Se encontraron " + coincidencias + " coindidencias de los caracteres " + enzimaActual[1]);
83+
System.out.println();
84+
}
85+
System.out.println("Busqueda finalizada");
86+
}
87+
88+
//Alamecna las enzimas de restriccion
89+
private ArrayList<String[]> almacenarEnzimas(File archivo) {
90+
ArrayList<String[]> enzimas = new ArrayList<>();
91+
try (BufferedReader reader = Files.newBufferedReader(archivo.toPath())) {
92+
String line = null;
93+
while ((line = reader.readLine()) != null) {
94+
String[] enzima = new String[2];
95+
int indice = 0;
96+
String nombreEnzima = "";
97+
while(line.charAt(indice) != ' ') {
98+
nombreEnzima += line.charAt(indice);
99+
indice++;
100+
}
101+
enzima[0] = nombreEnzima;
102+
String dataEnzima = "";
103+
indice++;
104+
while(indice < line.length()) {
105+
dataEnzima += line.charAt(indice);
106+
indice++;
107+
}
108+
enzima[1] = dataEnzima.toLowerCase();
109+
enzimas.add(enzima);
110+
}
111+
} catch (IOException x) {
112+
//throw new IOException("El archivo " + archivo.getPath() + " no se pudo leer");
113+
}
114+
return enzimas;
115+
}
116+
117+
private int fuerzaBruta(String strTexto, String strPatron, int enzima) {
118+
int busquedaActual = 0;
119+
int coincidencias = 0;
120+
char[] texto = strTexto.toCharArray();
121+
char[] patron = strPatron.toCharArray();
122+
int endPos = texto.length - patron.length+1;
123+
OUTER:
124+
for(int pos = 0; pos < endPos; pos++) {
125+
for(int i = 0; i < patron.length; i++) {
126+
if(texto[pos + i] != patron[busquedaActual]) {
127+
pos += (busquedaActual == 0) ? busquedaActual : busquedaActual - 1;
128+
busquedaActual = this.tablasKMPIndex.get(enzima)[busquedaActual];
129+
continue OUTER;
130+
}
131+
busquedaActual++;
132+
}
133+
System.out.println("Coincidencia en la posición: " + pos);
134+
coincidencias++;
135+
pos += busquedaActual - 1;
136+
busquedaActual = 0;
137+
}
138+
return coincidencias;
139+
}
140+
141+
//Procesar archivo de busqueda
142+
private String convertFile(File archivo) {
143+
BufferedReader lector;
144+
StringBuilder builder = new StringBuilder();
145+
String ultimo = null;
146+
try {
147+
lector = new BufferedReader(new FileReader(archivo));
148+
String linea = lector.readLine();
149+
while (linea != null) {
150+
int blanks = 0;
151+
char[] line = linea.toCharArray();
152+
for (int i = 10; i < line.length; i++) {
153+
if (Character.isWhitespace(line[i])) {
154+
blanks++;
155+
}
156+
}
157+
char[] newLine = new char[line.length - (10 + blanks)];
158+
int cont = 0;
159+
for (int i = 10; i < line.length; i++) {
160+
if (!Character.isWhitespace(line[i])) {
161+
newLine[cont] = line[i];
162+
cont++;
163+
}
164+
165+
}
166+
builder.append(new String(newLine));
167+
linea = lector.readLine();
168+
if (linea.length() == 0) {
169+
break;
170+
}
171+
}
172+
} catch (FileNotFoundException e) {
173+
// TODO Auto-generated catch block
174+
e.printStackTrace();
175+
} catch (IOException e) {
176+
// TODO Auto-generated catch block
177+
e.printStackTrace();
178+
}
179+
ultimo = builder.toString();
180+
return ultimo;
181+
}
182+
183+
//Crea las tablas pertinentes y almacena la información de las enzimas
184+
public void crearTablas() {
185+
this.tablasKMP = new ArrayList<>();
186+
this.tablasKMPIndex = new ArrayList<>();
187+
188+
//Almacenar las enzimas en un arreglo con nombre y secuencia
189+
this.enzimas = this.almacenarEnzimas(this.enzimasRestriccion);
190+
191+
//Crea la tabla KMP para la enzima
192+
this.hacerMultiplesTablas();
193+
}
194+
195+
private void hacerUnicaTabla(int seleccion) {
196+
String[] enzimaActual = this.enzimas.get(seleccion);
197+
System.out.println("Creando tabla KMP para enzima " + enzimaActual[0]);
198+
System.out.println("Cadena: " + enzimaActual[1]);
199+
System.out.println();
200+
this.llenarTablas(enzimaActual[1]);
201+
this.imprimirKMP(this.tablasKMP.get(seleccion), seleccion);
202+
System.out.println("Tabla creada");
203+
System.out.println();
204+
System.out.println();
205+
206+
}
207+
208+
private void hacerMultiplesTablas() {
209+
for(int largo = 0; largo < this.enzimas.size(); largo++) {
210+
String[] enzimaActual = this.enzimas.get(largo);
211+
System.out.println("Creando tabla KMP para enzima " + enzimaActual[0]);
212+
System.out.println("Cadena: " + enzimaActual[1]);
213+
System.out.println();
214+
this.llenarTablas(enzimaActual[1]);
215+
this.imprimirKMP(this.tablasKMP.get(largo), largo);
216+
System.out.println("Tabla creada");
217+
System.out.println();
218+
System.out.println();
219+
}
220+
}
221+
222+
private void llenarTablas(String patron) {
223+
String[][] tablaKMP = new String[3][patron.length()+1];
224+
int[] kmpTableIndex = new int[patron.length()+1];
225+
for(int charAt = 0; charAt < patron.length()+1; charAt++) {
226+
tablaKMP[0][charAt] = patron.substring(0, charAt);
227+
kmpTableIndex[charAt] = this.coincidenCaracteres(tablaKMP[0][charAt]);
228+
tablaKMP[1][charAt] = patron.substring(0, kmpTableIndex[charAt]);
229+
}
230+
this.tablasKMP.add(tablaKMP);
231+
this.tablasKMPIndex.add(kmpTableIndex);
232+
}
233+
234+
//Analiza si en un patron coinciden los caracteres
235+
private int coincidenCaracteres(String patron) {
236+
int coincidencias = 0;
237+
int largo = patron.length();
238+
int prefijoPosible = largo-1;
239+
int index = largo-2;
240+
while(index >= 0) {
241+
if(coincidencias > 0 && patron.charAt(index) != patron.charAt(prefijoPosible)) {
242+
index += coincidencias-1;
243+
coincidencias = 0;
244+
prefijoPosible = largo-1;
245+
}
246+
char h1 = patron.charAt(index);
247+
char h2 = patron.charAt(prefijoPosible);
248+
if(h1 == h2) {
249+
coincidencias++;
250+
prefijoPosible--;
251+
}
252+
index--;
253+
}
254+
return coincidencias;
255+
}
256+
257+
private void imprimirKMP(String[][] tablaKMP, int nTablasIndex) {
258+
System.out.println("Imprimiendo tabla: ");
259+
System.out.println();
260+
for(int i = 0; i < tablaKMP.length; i++) {
261+
System.out.print(i + " ");
262+
System.out.print(tablaKMP[0][i] + " ");
263+
System.out.print(tablaKMP[1][i] + " ");
264+
System.out.print(this.tablasKMPIndex.get(nTablasIndex)[i]);
265+
System.out.println();
266+
}
267+
System.out.println();
268+
}
269+
270+
public static void main(String[] args) {
271+
DNAStringMatching dsm = new DNAStringMatching();
272+
dsm.ingresaTexto();
273+
dsm.procesarArchivo();
274+
dsm.crearTablas();
275+
dsm.busquedaGeneral(0);
276+
dsm.busquedaGeneral(1);
277+
dsm.busquedaGeneral(2);
278+
}
279+
}

0 commit comments

Comments
 (0)