Member Avatar for i4ba1

Hai all,

I'm being create a dictionary. In the dictionary have feature search the word. if user entering the character "g" the word view in JList will show the word begin with "g". i try this first using Linier Search, it found the word, but linier. i mean if i input the "g" the view not show the word with begin "g", but i must type the next character to find the exact word. but i want if the user input g, the related word that begin with g will show for the first in JList. below i put my screenshoot. the first is when i open the sample dictionary and the second image if i enter the g the list will change to view the word begin with g. How can i create the search like that?please help me!!.

Best Regards

dictionari_2.jpg 35.54 KB dictionary_1.jpg 34.38 KB
  • 2 Contributors
  • 2 Replies
  • 1K Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by i4ba1
Member Avatar for ~s.o.s~

The simplest solution would be to use the "startsWith" method of the String class and inspect each and every dictionary entry whether it starts with the user input. But this approach can become unwieldy if the dictionary has a *lot* of entries since it means scanning the entire dictionary for every character entered by the user. Look into the "trie" data structure which is meant for exactly these kind of use cases if the "startsWith" solution doesn't suit your needs.

Member Avatar for i4ba1

The simplest solution would be to use the "startsWith" method of the String class and inspect each and every dictionary entry whether it starts with the user input. But this approach can become unwieldy if the dictionary has a *lot* of entries since it means scanning the entire dictionary for every character entered by the user. Look into the "trie" data structure which is meant for exactly these kind of use cases if the "startsWith" solution doesn't suit your needs.

I have success create the search, using ternary search algorithm. but, not complete. still some bugs. the bugs is there is no traversal tree algorithm when user input the textfield, it cause i'm confused how to create it?. maybe you can help me to find out the problem. here is, i include my source code. you can try to find out the problem and me to. if you find the solution please, tell me.

Thanks a lot

import java.awt.Color;
import java.awt.Rectangle;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.KeyEvent;
import java.awt.event.KeyListener;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

import java.sql.Connection;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Dictionary;
import java.util.List;
import java.util.Vector;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JList;
import javax.swing.JOptionPane;
import javax.swing.JPanel;
import javax.swing.JScrollPane;
import javax.swing.JTextField;
import javax.swing.border.TitledBorder;

import org.h2.command.dml.Optimizer;

public class frmKamus extends JFrame implements ActionListener, KeyListener {

	private static JTextField tfSearch;
	private JButton bSearch;
	private static JList lEn, lId;
	private List<String> words;
	private JScrollPane bar;
	private Vector<String> ketemu;
	
	private static TTSearchEngine<String> engine;

	private void createGUI() throws Exception {
		JPanel panel = new JPanel();
		//engine = new TTSearchEngine<String>();
		
		// Load the word in
		words = loadWithDB();
		System.out.println("word tio array "+words.toArray());
		engine = new TTSearchEngine<String>(words);
		// arrayList
		//Collections.sort(words); // sort ArrayList required for binarySearch

		// TextField cari
		tfSearch = new JTextField();
		tfSearch.addKeyListener(this);

		// Button cari
		bSearch = new JButton("Cari");

		
		// TextArea
		lEn = new JList();
		lEn.setAutoscrolls(true);
		lEn.setForeground(Color.BLACK);
		//lEn.setBounds(10, 70, 120, 270);
		lEn.setListData(words.toArray());
		
		bar = new JScrollPane(lEn);
		bar.setBounds(10, 70, 120, 270);
		lId = new JList();

		// Set Layout to null dan add panel to JFrame
		getContentPane().setLayout(null);
		getContentPane().add(panel);

		// Add tfSearch and bSearch to panel
		panel.add(tfSearch);
		panel.add(bSearch);
		panel.add(bar);
		//panel.add(lEn);
		

		// setting panel x,y,width, height
		panel.setBorder(new TitledBorder("Pencarian"));
		panel.setBounds(new Rectangle(5, 5, 300, 350));
		panel.setLayout(null);

		// setting componen x,y,width, height
		bSearch.setBounds(new Rectangle(215, 33, 60, 20));
		tfSearch.setBounds(new Rectangle(10, 30, 200, 25));

		setDefaultCloseOperation(EXIT_ON_CLOSE);
		setSize(320, 400);
		setVisible(true);
		setLocation(350, 250);
		setResizable(false);
	}

	public void keyPressed(KeyEvent e)
	{
		//System.out.println("pressed");
		String str = "";
		int keyCode = e.getKeyCode();
		str = str+KeyEvent.getKeyText(keyCode);
		
		List<String> list = engine.searchAll(str);
		lEn.setListData(list.toArray());
	}
	
	private int pencarianBiner(String key)
	{
		// Mencari bilangan N pada array A
	    // Kondisi awal : A harus diurut menaik (dari kecil ke besar)
	    // Kondisi akhir : Jika N ada dalam array, maka kembalikan
	    //    nilai i, di mana A[i] == N. Jika tidak kembalikan -1
		
		ketemu = new Vector<String>();
		int lokasiTerkecil = 0;
		int lokasiTerbesar = words.size()-1;
		while(lokasiTerbesar >= lokasiTerkecil)
		{
			
			int tengah = (lokasiTerkecil+lokasiTerbesar)/2;
			
			if (key.compareTo(words.get(tengah)) < 0) {
				lokasiTerbesar = tengah;
			}
			else if (key.compareTo(words.get(tengah)) > 0) {
				lokasiTerkecil = tengah + 1;
			}
			else
			{
				String word = ((String) words.get(tengah)).toLowerCase();
				ketemu.add(word);
				return tengah;
			}
		}
		
		return -1;
	}

	@Override
	public void actionPerformed(ActionEvent e) {
		// TODO Auto-generated method stub

	}

	private static Vector<String> loadFile(String fileName) throws Exception {
		String word;
		Vector<String> wordList = new Vector<String>();
		
		
		/*File file = new File(fileName);
		BufferedReader bfreader = new BufferedReader(new InputStreamReader(
				new FileInputStream(file)));
		
		
		while ((word = bfreader.readLine()) != null) {
			wordList.add(word.toLowerCase());

		}*/

		return wordList;

	}
	
	private static List<String> loadWithDB() throws Exception {
		String word, meaning;
		//Vector<String> kata = new Vector<String>();
		//Vector<String> arti = new Vector<String>();
		List<String> kata = new ArrayList<String>();
		
		Koneksi koneksi = new Koneksi();
		Connection con = koneksi.konekToDB();
		
		String sql = "select * from english";
		PreparedStatement ps = con.prepareStatement(sql);
		ResultSet rs = ps.executeQuery();
		
		while(rs.next())
		{
			//System.out.println("rs.getString(2) "+rs.getString(2));
			kata.add(rs.getString(2));
		}
		
		System.out.println("berhasil select query");
		//con.close();
		
		/*File file = new File(fileName);
		BufferedReader bfreader = new BufferedReader(new InputStreamReader(
				new FileInputStream(file)));
		
		
		while ((word = bfreader.readLine()) != null) {
			wordList.add(word.toLowerCase());

		}*/

		return kata;

	}

	public static void main(String[] args) throws Exception {

		frmKamus kamus = new frmKamus();
		kamus.createGUI();
	}

	@Override
	public void keyReleased(KeyEvent arg0) {
		// TODO Auto-generated method stub

	}

	@Override
	public void keyTyped(KeyEvent arg0) {
		// TODO Auto-generated method stub

	}
}
import java.util.List;
/**
 * This class is used to suggest a list of items, which will be similar to a
 * given string prefix.
 */
public interface SearchEngine<E> {
	/**
	 * Returns a list of elements, which will be similar to a given string
	 * prefix.
	 * 
	 * @param prefix
	 *            String prefix to match against elements
	 * @return A list of E elements, which will be similar to a given string
	 *         prefix. Returns empty list if no match found.
	 */

	public List<E> searchAll(String prefix);

	/**
	 * Returns an element, which will be most similar to a given string prefix.
	 * 
	 * @param prefix
	 *            String prefix to match against elements
	 * @return An element, which will be most similar to a given string prefix.
	 *         Returns <code>null</code> if no match found.
	 */
	
	public E Search(String prefix);
}
/*
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or (at
 * your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 * Copyright (C) 2008 Cheok YanCheng <yccheok@yahoo.com>
 * 
 * Modified by Yan Cheng for generic introduction and thread safe matchPrefix.
 * Original Author Wally Flint: wally@wallyflint.com
 * With thanks to Michael Amster of webeasy.com for introducing Wally Flint to 
 * the Ternary Search Tree, and providing some starting code.
 */

import java.util.*;

/**
 * Implementation of ternary search tree. A Ternary Search Tree is a data
 * structure that behaves in a manner that is very similar to a HashMap.
 */
public class TernarySearchTree<E> {
	private TSTNode<E> rootNode;
	private int defaultNumReturnValues = -1;

	/**
	 * Stores value in the TernarySearchTree. The value may be retrieved using
	 * key.
	 * 
	 * @param key
	 *            A string that indexes the object to be stored.
	 * @param value
	 *            The object to be stored in the tree.
	 */
	public void put(String key, E value) {
		getOrCreateNode(key).data = value;
	}

	/**
	 * Retrieve the object indexed by key.
	 * 
	 * @param key
	 *            A String index.
	 * @return Object The object retrieved from the TernarySearchTree.
	 */
	public E get(String key) {
		TSTNode<E> node = getNode(key);
		if (node == null)
			return null;
		return node.data;
	}

	/**
	 * Removes value indexed by key. Also removes all nodes that are rendered
	 * unnecessary by the removal of this data.
	 * 
	 * @param key
	 *            A string that indexes the object to be removed from the tree.
	 */
	public E remove(String key) {
		TSTNode<E> node = getNode(key);
		deleteNode(getNode(key));
		return (node != null ? node.data : null);
	}

	/**
	 * Sets default maximum number of values returned from matchPrefix,
	 * matchPrefixString, matchAlmost, and matchAlmostString methods.
	 * 
	 * @param num
	 *            The number of values that will be returned when calling the
	 *            methods above. Set this to -1 to get an unlimited number of
	 *            return values. Note that the methods mentioned above provide
	 *            overloaded versions that allow you to specify the maximum
	 *            number of return values, in which case this value is
	 *            temporarily overridden.
	 */
	public void setNumReturnValues(int num) {
		defaultNumReturnValues = (num < 0) ? -1 : num;
	}

	private int checkNumberOfReturnValues(int numReturnValues) {
		return ((numReturnValues < 0) ? -1 : numReturnValues);
	}

	/**
	 * Returns the Node indexed by key, or null if that node doesn't exist.
	 * Search begins at root node.
	 * 
	 * @param key
	 *            An index that points to the desired node.
	 * @return TSTNode The node object indexed by key. This object is an
	 *         instance of an inner class named TernarySearchTree.TSTNode.
	 */
	public TSTNode<E> getNode(String key) {
		return getNode(key, rootNode);
	}

	/**
	 * Returns the Node indexed by key, or null if that node doesn't exist.
	 * Search begins at root node.
	 * 
	 * @param key
	 *            An index that points to the desired node.
	 * @param startNode
	 *            The top node defining the subtree to be searched.
	 * @return TSTNode The node object indexed by key. This object is an
	 *         instance of an inner class named TernarySearchTree.TSTNode.
	 */
	protected TSTNode<E> getNode(String key, TSTNode<E> startNode) {
		if (key == null || startNode == null || key.length() == 0)
			return null;
		TSTNode<E> currentNode = startNode;
		int charIndex = 0;

		while (true) {
			if (currentNode == null)
				return null;
			int charComp = compareCharsAlphabetically(key.charAt(charIndex),
					currentNode.splitchar);

			if (charComp == 0) {
				charIndex++;
				if (charIndex == key.length())
					return currentNode;
				currentNode = currentNode.relatives[TSTNode.EQKID];
			} else if (charComp < 0) {
				currentNode = currentNode.relatives[TSTNode.LOKID];
			} else {
				// charComp must be greater than zero
				currentNode = (TSTNode<E>) currentNode.relatives[TSTNode.HIKID];
			}
		}
	}

	public List<E> matchPrefix(String prefix) {
		return matchPrefix(prefix, defaultNumReturnValues);
	}

	public List<E> matchPrefix(String prefix, int numReturnValues) {
		int sortKeysNumReturnValues = checkNumberOfReturnValues(numReturnValues);
		List<E> sortKeysResult = new ArrayList<E>();
		
		TSTNode<E> startNode = getNode(prefix);

		if (startNode == null)
			return sortKeysResult;
		if (startNode.data != null) {
			sortKeysResult.add(startNode.data);
			sortKeysNumReturnValues--;
		}

		sortKeysRecursion(sortKeysResult, startNode.relatives[TSTNode.EQKID],
				sortKeysNumReturnValues);

		return sortKeysResult;
	}

	private void sortKeysRecursion(List<E> sortKeysResult,
			TSTNode<E> currentNode, int sortKeysNumReturnValues) {
		if (currentNode == null)
			return;
		sortKeysRecursion(sortKeysResult, currentNode.relatives[TSTNode.LOKID],
				sortKeysNumReturnValues);
		if (sortKeysNumReturnValues == 0)
			return;

		if (currentNode.data != null) {
			sortKeysResult.add(currentNode.data);
			sortKeysNumReturnValues--;
		}

		sortKeysRecursion(sortKeysResult, currentNode.relatives[TSTNode.EQKID],
				sortKeysNumReturnValues);
		sortKeysRecursion(sortKeysResult, currentNode.relatives[TSTNode.HIKID],
				sortKeysNumReturnValues);
	}

	protected List<E> sortKeys(TSTNode<E> startNode, int numReturnValues) {
		int sortKeysNumReturnValues = checkNumberOfReturnValues(numReturnValues);
		List<E> sortKeysResult = new ArrayList<E>();
		sortKeysRecursion(sortKeysResult, startNode, sortKeysNumReturnValues);
		return sortKeysResult;
	}

	/**
	 * Returns the Node indexed by key, creating that node if it doesn't exist,
	 * and creating any required. intermediate nodes if they don't exist.
	 * 
	 * @param key
	 *            A string that indexes the node that is returned.
	 * @return TSTNode The node object indexed by key. This object is an
	 *         instance of an inner class named TernarySearchTree.TSTNode.
	 */
	protected TSTNode<E> getOrCreateNode(String key)
			throws NullPointerException, IllegalArgumentException {
		if (key == null)
			throw new NullPointerException(
					"attempt to get or create node with null key");
		if (key.length() == 0)
			throw new IllegalArgumentException(
					"attempt to get or create node with key of zero length");
		if (rootNode == null)
			rootNode = new TSTNode<E>(key.charAt(0), null);

		TSTNode<E> currentNode = rootNode;
		int charIndex = 0;
		while (true) {
			int charComp = compareCharsAlphabetically(key.charAt(charIndex),
					currentNode.splitchar);

			if (charComp == 0) {
				charIndex++;
				if (charIndex == key.length())
					return currentNode;
				if (currentNode.relatives[TSTNode.EQKID] == null)
					currentNode.relatives[TSTNode.EQKID] = new TSTNode<E>(
							key.charAt(charIndex), currentNode);
				currentNode = currentNode.relatives[TSTNode.EQKID];
			} else if (charComp < 0) {
				if (currentNode.relatives[TSTNode.LOKID] == null)
					currentNode.relatives[TSTNode.LOKID] = new TSTNode<E>(
							key.charAt(charIndex), currentNode);
				currentNode = currentNode.relatives[TSTNode.LOKID];
			} else {
				// charComp must be greater than zero
				if (currentNode.relatives[TSTNode.HIKID] == null)
					currentNode.relatives[TSTNode.HIKID] = new TSTNode<E>(
							key.charAt(charIndex), currentNode);
				currentNode = currentNode.relatives[TSTNode.HIKID];
			}
		}
	}

	/*
	 * Deletes the node passed in as an argument to this method. If this node
	 * has non-null data, then both the node and the data will be deleted. Also
	 * deletes any other nodes in the tree that are no longer needed after the
	 * deletion of the node first passed in as an argument to this method.
	 */
	private void deleteNode(TSTNode<E> nodeToDelete) {
		if (nodeToDelete == null)
			return;
		nodeToDelete.data = null;

		while (nodeToDelete != null) {
			nodeToDelete = deleteNodeRecursion(nodeToDelete);
		}
	}

	private TSTNode<E> deleteNodeRecursion(TSTNode<E> currentNode) {
		// To delete a node, first set its data to null, then pass it into this
		// method, then pass the node returned by this method into this method
		// (make sure you don't delete the data of any of the nodes returned
		// from this method!)
		// and continue in this fashion until the node returned by this method
		// is null.
		// The TSTNode instance returned by this method will be next node to be
		// operated on by deleteNodeRecursion.
		// (This emulates recursive method call while avoiding the JVM overhead
		// normally associated with a recursive method.)

		if (currentNode == null)
			return null;
		if (currentNode.relatives[TSTNode.EQKID] != null
				|| currentNode.data != null)
			return null; // can't delete this node if it has a non-null eq kid
							// or data

		TSTNode<E> currentParent = currentNode.relatives[TSTNode.PARENT];

		// if we've made it this far, then we know the currentNode isn't null,
		// but its data and equal kid are null, so we can delete the current
		// node
		// (before deleting the current node, we'll move any lower nodes higher
		// in the tree)
		boolean lokidNull = currentNode.relatives[TSTNode.LOKID] == null;
		boolean hikidNull = currentNode.relatives[TSTNode.HIKID] == null;

		// //////////////////////////////////////////////////////////////////////
		// Add by Cheok. To resolve java.lang.NullPointerException
		// I am not sure this is the correct solution, as I have not gone
		// through this sourc code in detail.
		if (currentParent == null && currentNode == this.rootNode) {
			// if this executes, then current node
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * This class is used to suggest a list of items, which will be similar to a
 * given string prefix. Tenary Search Tree will be the primary data structure to
 * hold the complete list of E items. The searching mechanism is case
 * insensitive.
 */

public class TTSearchEngine<E> implements SearchEngine<E> {

	private final TernarySearchTree<String> tst = new TernarySearchTree<String>();

	// We need to have this map, so that we are able to retrieve E value
	// in a case insensitive way. This is just a pseudo way for us to
	// achieve this purpose. We should really build this case insensitive
	// capability into TernarySearchTree itself. Once TernarySearchTree
	// has the capability to handle case insensitive, it should be holding
	// E value instead of String (String will be used as the key to access
	// map).
	//
	// There should be no duplicated item in List. Don't use Set, as order
	// is important for us.
	private final Map<String, List<E>> map = new HashMap<String, List<E>>();

	/**
	 * Initializes a newly created {@code TSTSearchEngine} with a given list of
	 * elements.
	 * 
	 * @param sources
	 *            List of elements used to fill up {@code TSTSearchEngine}
	 */
	public TTSearchEngine(List<E> source) {
		for (E e : source) {
			put(e);
		}
	}

	/**
	 * Initializes a newly created {@code TSTSearchEngine} with empty element.
	 */
	public TTSearchEngine() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * Insert an element into this search engine.
	 * 
	 * @param value
	 *            Element to be inserted
	 */
	public final void put(E value) {
		// TODO Auto-generated method stub
		/**
		 * Insert an element into this search engine.
		 * 
		 * @param value
		 *            Element to be inserted
		 */

		final String mapKey = value.toString().toUpperCase();
		// /System.out.println("mapKey "+mapKey);
		tst.put(mapKey, mapKey);

		List<E> list = map.get(mapKey);
		
		if (list == null) {
			list = new ArrayList<E>();
			map.put(mapKey, list);
		}

		// Avoid duplication. Don't use Set, as order is
		// important for us.
		if (false == list.contains(value)) {
			list.add(value);
		}
	}

	/**
	 * Removes an element from this search engine.
	 * 
	 * @param value
	 *            Element to be removed
	 */
	public void remove(E value) {
		final String mapKey = value.toString().toLowerCase();
		final String key = tst.remove(mapKey);
		if (key != null) {
			map.remove(key);
		}
	}

	/**
	 * Returns a list of elements, which will be similar to a given string
	 * prefix. The searching mechanism is case insensitive.
	 * 
	 * @param prefix
	 *            String prefix to match against elements
	 * @return A list of elements, which will be similar to a given string
	 *         prefix. Returns empty list if no match found.
	 */
	@Override
	public List<E> searchAll(String prefix) {
		// TODO Auto-generated method stub
		System.out.print(prefix);
		final String mapKey = prefix.toUpperCase();
		final List<String> keys = tst.matchPrefix(mapKey);
		final List<E> list = new ArrayList<E>();
		
		for (String key : keys) {
			// map.get(key) must be non-null.
			list.addAll(map.get(key));
		}
		
		return list;
	}

	/**
	 * Returns an element, which will be most similar to a given string prefix.
	 * The searching mechanism is case insensitive.
	 * 
	 * @param prefix
	 *            String prefix to match against elements
	 * @return An element, which will be most similar to a given string prefix.
	 *         Returns <code>null</code> if no match found.
	 */
	@Override
	public E Search(String prefix) {
		// TODO Auto-generated method stub
		final String mapKey = prefix.toUpperCase();
		final List<String> keys = tst.matchPrefix(mapKey);

		if (keys.isEmpty() == false) {
			final String key = keys.get(0);

			// key must be non null!!
			final List<E> l = map.get(key);
			if (l.isEmpty() == false) {
				System.out.println(l.get(0));
				return l.get(0);
			} else {
				return null;
			}

		}
		return null;
	}

}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.