algoritmo

.Net: Classe para pesquisa de arquivos assíncrona e com múltiplos filtros – C#

Olá Pessoal,

Esse é o meu último dia de férias do trabalho (choro eterno), e acabei escrevendo um código para uma contribuição no MSDN que achei que seria interessante publicar.

É uma classe para pesquisa de arquivos assíncrona e que permite o uso de múltiplos filtros (de forma simultânea, na qual só serão retornados os resultados que satisfizerem a todos os filtros, de forma normal, onde serão retornados os arquivos que atendem a qualquer um dos filtros, mesmo que só um).

É um código simples, mas que na pressa, vale um Ctrl + C Ctrl + V. Enfim, segue o código:

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

namespace HL.IO
{
    public class FileSearch
    {
        private string[] _Filters;
        public string[] Filters
        {
            get { return _Filters; }
            set { _Filters = value; }
        }

        private SearchOptions _SearchOption;
        public SearchOptions SearchOption
        {
            get { return _SearchOption; }
            set { _SearchOption = value; }
        }

        public FileSearch(SearchOptions SearchOption, params string[] Filters)
        {
            _Filters = Filters;
            _SearchOption = SearchOption;
        }
        public FileSearch()
        {
            _SearchOption = SearchOptions.AllDirectories | SearchOptions.MatchAllFilters;
            _Filters = null;
        }
        public IEnumerable<string> Search(string RootFolder)
        {
            if (_SearchOption.HasFlag(SearchOptions.AllDirectories))
            {
                IEnumerable<string> result = Directory.EnumerateFiles(RootFolder, "*.*", System.IO.SearchOption.AllDirectories);
                if (_SearchOption.HasFlag(SearchOptions.MatchAllFilters))
                    return result.Where(s => Path.GetFileName(s).ContainsAll(_Filters,
                        _SearchOption.HasFlag(SearchOptions.CaseSensitive)));
                else
                    return result.Where(s => Path.GetFileName(s).ContainsAny(_Filters,
                        _SearchOption.HasFlag(SearchOptions.CaseSensitive)));
            }
            else
            {
                IEnumerable<string> result = Directory.EnumerateFiles(RootFolder, "*.*", System.IO.SearchOption.TopDirectoryOnly);
                if (_SearchOption.HasFlag(SearchOptions.MatchAllFilters))
                    return result.Where(s => Path.GetFileName(s).ContainsAll(_Filters,
                        _SearchOption.HasFlag(SearchOptions.CaseSensitive)));
                else
                    return result.Where(s => Path.GetFileName(s).ContainsAny(_Filters,
                        _SearchOption.HasFlag(SearchOptions.CaseSensitive)));
            }
        }

        #region Async
        public void AsyncSearch(string RootFolder)
        {
            SynchronizationContext context = SynchronizationContext.Current;
            if (context == null)
            {
                context = new System.Threading.SynchronizationContext();
            }
            Thread th = new Thread(new ThreadStart(() =>
            {
                IEnumerable<string> result = Search(RootFolder);
                context.Send(new SendOrPostCallback((object state) =>
                {
                    OnAsyncSearchCompleted((IEnumerable<string>)state);
                }), result);
            }));
            th.IsBackground = false;
            th.SetApartmentState(ApartmentState.STA);
            th.Start();
        }
        public event AsyncSearchCompletedEventHandler AsyncSearchCompleted;
        protected virtual void OnAsyncSearchCompleted(IEnumerable<string> Result)
        {
            if (AsyncSearchCompleted != null)
            {
                AsyncSearchCompleted(this, new AsyncSearchCompletedEventArgs(Result));
            }
        }
        #endregion
    }

    public delegate void AsyncSearchCompletedEventHandler(object sender, AsyncSearchCompletedEventArgs e);

    public class AsyncSearchCompletedEventArgs
    {
        private IEnumerable<string> _result;
        public IEnumerable<string> Result
        {
            get { return _result; }
        }
        public AsyncSearchCompletedEventArgs(IEnumerable<string> Result)
        {
            _result = Result;
        }
    }
    public enum SearchOptions : int
    {
        /// <summary>
        /// The search engine will seach only on top level of the given root folder.
        /// </summary>
        TopDirectoryOnly = 1,
        /// <summary>
        /// The search engine will search in all the directory tree starting from the given root folder
        /// </summary>
        AllDirectories = 2,
        /// <summary>
        /// The search engine will use case sensitive approach.
        /// </summary>
        CaseSensitive = 4,
        /// <summary>
        /// If set, the search engine will return only the results matching all the filters.
        /// </summary>
        MatchAllFilters = 8
    };
    public static class StringExtensions
    {
        public static bool ContainsAll(this string Source, string[] strs, bool CaseSensitive)
        {
            foreach (string str in strs)
            {
                if (CaseSensitive)
                {
                    if (!Source.Contains(str)) return false;
                }
                else
                {
                    if (!Source.ToLower().Contains(str.ToLower())) return false;
                }
            }
            return true;
        }

        public static bool ContainsAny(this string Source, string[] strs, bool CaseSensitive)
        {
            foreach (string str in strs)
            {
                if (CaseSensitive)
                {
                    if (Source.Contains(str)) return true;
                }
                else
                {
                    if (Source.ToLower().Contains(str.ToLower())) return true;
                }
            }
            return false;
        }
    }
}

Mostrarei também um pequeno exemplo:

        private void btnSearch_Click(object sender, EventArgs e)
        {
            FolderBrowserDialog dialog = new FolderBrowserDialog();
            dialog.ShowDialog();
            FileSearch searcher = new FileSearch(SearchOptions.AllDirectories, ".png", ".bmp", ".jpeg");
            searcher.AsyncSearchCompleted += searcher_AsyncSearchCompleted;
            searcher.AsyncSearch(dialog.SelectedPath);
        }

        private void searcher_AsyncSearchCompleted(object sender, AsyncSearchCompletedEventArgs e)
        {
            listBox1.Items.Clear();
            listBox1.Items.AddRange(e.Result.ToArray());
        }

No exemplo acima a classe FileSearch é usada para encontrar todos os arquivos PNG, BMP e JPEG da pasta informada. Isso é bem básico, mas dá para fazer bastante coisa. Incluir uma palavra chave que o nome do arquivo deve conter também é uma opção. E o melhor de tudo, assíncrono. Não irá congelar a interface de usuário enquanto realiza a busca.

That’s all folks!!!

Algoritmo para comparação de strings – C#

Olá pessoal, neste post vou apresentar um algoritmo para comparação de strings junto de uma implementação mais avançada que eu criei.

Bom, trata-se do algoritmo chamado Levenshtein-Distance, criado por um carinha chamado Vladimir Levenshtein. Segue o conceito básico do algorítimo:

Em teoria da informação, a distância Levenshtein ou distância de edição entre dois “strings” (duas sequências de caracteres) é dada pelo número mínimo de operações necessárias para transformar um string no outro. Entendemos por “operações” a inserção, deleção ou substituição de um carácter. O nome advém do cientista russo Vladimir Levenshtein, que considerou esta distância já em 1965. É muito útil para aplicações que precisam determinar quão semelhantes dois strings são, como é por exemplo o caso com os verificadores ortográficos.

Fonte: Distância Levenshtein – Wikipédia

Dado o conceito, agora irei apresentar o problema dele:

Digamos que nós temos as seguintes strings:

string a = "Herbert Lausmann";
string b = "Herbert Lausman";

string c = "Eu";
string d = "Tu";

Usando o algoritmo de Levenshtein vamos compara-las. Eis os resultados:

int ab = 1;
int cd = 1;

Perceba o seguinte: na primeira comparação o resultado foi 1 e na segunda comparação o resultado foi 1 também!

O algoritmo de Levenshtein retorna a distância entre duas strings (que no caso das duas é 1). Porém nós sabemos que ab são 50% semelhantes e cd são algo em torno de 95% semelhantes. Seria bem melhor se pudéssemos obter como resultado um valor em uma gama específica como por exemplo 0-100 onde 0 quer dizer que as strings são totalmente diferentes e 100 quer dizer que são totalmente iguais.

Pensando neste problema desenvolvi a classe estática abaixo:

using System;

namespace HL
{
    public static class HerbertLevenshteinAlgorithm
    {

        private static int LevenshteinDistance(string source, string target)
        {
            if (String.IsNullOrEmpty(source))
            {
                if (String.IsNullOrEmpty(target)) return 0;
                return target.Length;
            }
            if (String.IsNullOrEmpty(target)) return source.Length;

            if (source.Length > target.Length)
            {
                var temp = target;
                target = source;
                source = temp;
            }

            var m = target.Length;
            var n = source.Length;
            var distance = new int[2, m + 1];

            for (var j = 1; j <= m; j++) distance[0, j] = j;

            var currentRow = 0;
            for (var i = 1; i <= n; ++i)
            {
                currentRow = i & 1;
                distance[currentRow, 0] = i;
                var previousRow = currentRow ^ 1;
                for (var j = 1; j <= m; j++)
                {
                    var cost = (target[j - 1] == source[i - 1] ? 0 : 1);
                    distance[currentRow, j] = Math.Min(Math.Min(
                                distance[previousRow, j] + 1,
                                distance[currentRow, j - 1] + 1),
                                distance[previousRow, j - 1] + cost);
                }
            }
            return distance[currentRow, m];
        }

        /// <summary>
        /// Compara duas strings
        /// </summary>
        /// <param name="a">Primeira string</param>
        /// <param name="b">Segunda string</param>
        /// <returns>Retorna um valor de 0 à 255. Quanto mais alto este valor mais parecidas são as strings</returns>
        public static byte Compare(string a, string b)
        {
            double distance = LevenshteinDistance(a, b);
            if (distance == 0) return 255;
            double length = Math.Max(a.Length, b.Length);
            if (distance == length) return 0;

            double inverted = Invert(distance, length);
            byte percent = (byte)((inverted / length) * 255);
            return percent;
        }

        private static double Invert(double min, double max)
        {
            return max - min;
        }

    }
}

No caso da minha classe o método Compare(string a, string b) irá retornar um byte (com um valor de 0 à 255) onde quanto mais alto o valor mais parecidas são as strings.

Problema resolvido, agora temos um algoritmo realmente eficaz, o algoritmo de Herbert-Levenshtein. 😉

Vale citar a fonte onde eu peguei a implementação do algoritmo de Levenshtein:

Algorithm Implementation/Strings/Levenshtein distance – Wikibooks

Até mais!