VPF::частотный анализ слов встречающихся в файлах задан

rurik

Дата 16.10.2011, 21:26 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 9.4.2011

Репутация: нет
Всего: нет

Здравствуйте,подскажите как лучше написать алгоритм подсчета слов всех файлов в заданной директории.(пишу на Java)

т.е. необходимо пройти по всем файлам в директории(или несколько директорий или директория + файл .на входе массив адресов относительно диска С) , разбить все файлы на слова, посчитать количество раз которое встречается каждое слово и вывести все слова с их счетчиками отсортировав по значению счетчика.

подскажите как лучше построить алгоритм, общие мысли), может советы, если что то более детальное еще больше благодарен буду) чтобы он получился наиболее оптимальным, быстрее работал

Akina

Дата 16.10.2011, 23:10 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

Обычная сортировка подсчётом. Слова строить в обычное бин. дерево. Если прогнозируется значительный процент уникальных слов - возможно, параллельно строить суффиксное дерево для быстрой проверки на униакльность.

--------------------

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

rurik

Дата 17.10.2011, 12:54 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 9.4.2011

Репутация: нет
Всего: нет

Расскажите поподробнее о том как именно строить слова в бинарное дерево

esperanto

Дата 17.10.2011, 16:21 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 194
Регистрация: 31.5.2003

Репутация: 2
Всего: 4

TRIE дерево с дополнительным полем для подсчета, имхо более подходит

--------------------

B.Sc ->M.Sc.->Microsoft SDE-> (Ph.D. student + Intel SDE + psyсhology B.A) - > Skype SDET

Akina

Дата 17.10.2011, 16:27 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

Цитата(rurik @ 17.10.2011, 13:54

)

как именно строить слова в бинарное дерево

http://ru.wikipedia.org/wiki/B-%D0%B4%D0%B...%B5%D0%B2%D0%BE

--------------------

Silent

Дата 18.10.2011, 12:37 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 252
Регистрация: 3.10.2006

Репутация: 1
Всего: 9

Возможен еще вариант написать MapReduce на map'е, сразу в несколько потоков забубенить. Для примера код на C# (но кажется, где-то есть ошибочка):

Код


using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Threading;

namespace MapReduce
{
    class Program
    {
        struct elem
        {
            public string input,
                   output;
        }

        const int max_threads = 20;
        static int count_runs = 0;
        static Queue<Thread> threads = new Queue<Thread>();
        static Queue<elem> paths = new Queue<elem>();
        //static Queue<string> input   = new Queue<string>();
        //static Queue<string> output  = new Queue<string>();

        static char[] terms = { ' ', '.', ',', '?', '!', '-' };
        const string dirTXT = @"z:\TMP\txt\";    //каталог, откуда будут выдираться тексты
        const string dirDAT = @"z:\TMP\dat\";    //каталог, куда будут складываться обработанные файлы
        const string dirTMP = @"z:\TMP\tmp\";    //каталог, куда будут временно складываться файлы для обработки

        //главный поток обработки текстов
        static void Main(string[] args)
        {
            Console.WriteLine("Starting...");
            int i = 0;
            bool flag = true;
            while (!Console.KeyAvailable && flag)
            {
                FileInfo[] files = (new DirectoryInfo(dirTXT)).GetFiles("*.txt");
                int count = 0;
                foreach (FileInfo f in files)
                {
                    Thread t = new Thread(start);
                    threads.Enqueue(t);
                    elem a;
                    f.MoveTo(dirTMP + Path.GetFileName(f.FullName));
                    a.input = f.FullName;
                    a.output = dirDAT + i.ToString() + ".dat";
                    paths.Enqueue(a);
                    i++;
                    count++;
                }
                if (count != 0)
                    Console.WriteLine("Add " + count.ToString() + " files");
                //вручную запустим цикл обработки
                if (threads.Count > 0)
                {
                    lock (threads)
                        lock (paths)
                        {
                            Thread t = threads.Dequeue();
                            elem a = paths.Dequeue();
                            count_runs++;
                            t.Start(a);
                        }

                }
                if (Console.KeyAvailable) flag = Console.ReadKey().Key != ConsoleKey.Escape;
            }
        }

        /// <summary>
        /// Обработка файла input, результаты записывем в файл output
        /// </summary>
        static void start(object data)//string input, string output)
        {
            elem a = (elem)data;
            StreamReader fin = new StreamReader(a.input);
            SortedList<string, int> list = new SortedList<string, int>();
            //считаем файл в сортированный список
            while (!fin.EndOfStream)
            {
                foreach (string t in fin.ReadLine().Split(terms))
                    if (list.ContainsKey(t)) list[t]++;
                    else list.Add(t, 1);
            }
            //сбросим результат в файл
            StreamWriter fout = new StreamWriter(a.output);
            foreach (string t in list.Keys)
                fout.WriteLine(t + " " + list[t].ToString());
            fout.Close();
            fin.Close();
            FileInfo f = new FileInfo(a.input);
            f.Delete();
            Console.WriteLine(Path.GetFileName(a.input) + " -> " + Path.GetFileName(a.output));
            //удалим себя из количества выполняющихся потоков
            count_runs--;
            //и скажем, чтобы менеджер попытался запустить далее
            lock (threads)
                while ((count_runs < max_threads) && (threads.Count > 0))
                {
                    if (threads.Count > 0)
                    {
                        lock (threads)
                            lock (paths)
                            {
                                Thread t = threads.Dequeue();
                                elem obj = paths.Dequeue();
                                t.Start(obj);
                                count_runs++;
                            }
                    }
                }
        }
    }
}

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »