Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Java: Общие вопросы > Правильный способ искать слово в текстовом файле

Автор: Mikail 11.2.2008, 02:29

Как правильно с помощью java искать в текстовом файле некое слово. Допустим, в текстовом файле 1000000 строк по 40-50 символов. Как оптимально быстро и грамотно найти слово в этом массиве при минимальном расходе оперативки?

Автор: Aizek 11.2.2008, 02:42

Можно глупо читать строку и проверять наличие типа indexOf(). Если будет не отрицательное значение, слово найдено.

Автор: nornad 11.2.2008, 03:52

Что значит "найти"? Вам необходимо установить сам факт наличия слова в тексте, отыскать позицию первого вхождения или вообще получить список позиций всех вхождений?
Для первого случая достаточно запуска утилиты grep на файле. Во втором и третьем придётся читать файл. Наименьший объём памяти при этом будет именно при построчном считывании.

Автор: powerOn 11.2.2008, 11:56

А если задача подразумевает неоднократный поиск по редко изменяемым данным, то лучше использовать индексирование. Например http://lucene.apache.org/ будет весьма кстати.

Автор: Mikail 11.2.2008, 20:20

Спасибо всем за советы, но построчное считываение с проверкой index0f слишком медленное.
По условию задачи надо отыскать первое вхождение искомого в файле. Как это сделать максимально быстро?
Готовая поисковая система - слишком тяжелое решение.

Автор: Sardar 11.2.2008, 20:59

Если нужно с минимальными затратами к памяти, то можно искать хешем, даже без буфферизации побайтовым чтением (что будет медленно), http://algolist.manual.ru/search/esearch/karp_rab.php. Если нужна именно скорость, то http://algolist.manual.ru/search/esearch/turbo_bm.php по моему самое скоростное.

Автор: niasilil 11.2.2008, 23:29

Совершенно неважно сколько будет сравнений в памяти, какой алгоритм оптимизации этих сравнений и тд. Важно только количество IO операций (каждая 5ms или около того). Соответственно, минимизировать это количество - первоочередная задача. Как вариант - RandomAccessFile. Читаешь скажем 100к-500к в байт массив, создаешь из него StringBuilder и пользуешь indexOf. Все должно летать и работать с маленькими объемами памяти если не забыть пересипользовать тот же самый массив и StringBuilder объект.

ну либо с помощью grep, как nornad выше сказал. Но я про nio почти ничего знаю.

Автор: niasilil 12.2.2008, 00:08

кстати, BufferedReader тоже может прочитать мегабайт за раз и образовать char[] array. Вот его в стринг билдер и суй.

Код


        final int SIZE = 100000;
        FileReader fr = new FileReader("test.txt");
        BufferedReader br = new BufferedReader(fr, SIZE);

        char[] b = new char [SIZE];
        br.read(b, 0, b.length);

        StringBuilder sb = new StringBuilder();
        sb.setLength(0);
        sb.append(b);

        System.out.println(sb.indexOf("blah"));

ну и циклы, проверки и т.д.

Автор: Mikail 12.2.2008, 23:16

Огромне всем спасибо!

Автор: niasilil 13.2.2008, 01:38

Цитата(Mikail @ 12.2.2008, 23:16)

Огромне всем спасибо!

Не забудь ситуацию когда половина искомого слова приходится на первый прочитанный блок, а вторая часть на другой. То если ищешь "blahblah", а в первом блоке только "bla" а во втрором "hblah", то надо бы второй блок читать не с 100000 позиции, а только с (100000 - 8). Легко забыть и ошибка не сразу всплывет.