c# - lista - prefijo comun

Encontrar el prefijo común de las cadenas

Question

Estoy teniendo 4 cadenas:

"h:/a/b/c"
"h:/a/b/d"
"h:/a/b/e"
"h:/a/c"

Quiero encontrar el prefijo común para esas cadenas, es decir, "h:/a" . ¿Cómo encontrar eso?

Por lo general, dividía la cadena con el delimitador ''/'' y lo colocaba en otra lista, y así sucesivamente.
¿Hay alguna forma mejor de hacerlo?

Answer 1

Aquí hay una implementación personalizada del algoritmo trie en c # ( http://en.wikipedia.org/wiki/Trie ). Se usa para realizar una cadena indexada a través de prefijos. Esta clase tiene O (1) escribe y lee para nodos hoja. Para las búsquedas de prefijos, el rendimiento es O (log n), sin embargo, el recuento de resultados para el prefijo es O (1).

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

public class StringIndex
{
    private Dictionary<char, Item> _rootChars;

    public StringIndex()
    {
        _rootChars = new Dictionary<char, Item>();
    }

    public void Add(string value, string data)
    {
        int level = 0;
        Dictionary<char, Item> currentChars = _rootChars;
        Item currentItem = null;

        foreach (char c in value)
        {
            if (currentChars.ContainsKey(c))
            {
                currentItem = currentChars[c];
            }
            else
            {
                currentItem = new Item() { Level = level, Letter = c };
                currentChars.Add(c, currentItem);                
            }

            currentChars = currentItem.Items;

            level++;
        }

        if (!currentItem.Values.Contains(data))
        {
            currentItem.Values.Add(data);
            IncrementCount(value);
        }
    }

    private void IncrementCount(string value)
    {
        Dictionary<char, Item> currentChars = _rootChars;
        Item currentItem = null;

        foreach (char c in value)
        {
            currentItem = currentChars[c];
            currentItem.Total++;
            currentChars = currentItem.Items;
        }
    }

    public void Remove(string value, string data)
    {
        Dictionary<char, Item> currentChars = _rootChars;
        Dictionary<char, Item> parentChars = null;
        Item currentItem = null;

        foreach (char c in value)
        {
            if (currentChars.ContainsKey(c))
            {
                currentItem = currentChars[c];
                parentChars = currentChars;
                currentChars = currentItem.Items;
            }
            else
            {
                return; // no matches found
            }
        }

        if (currentItem.Values.Contains(data))
        {
            currentItem.Values.Remove(data);
            DecrementCount(value);
            if (currentItem.Total == 0)
            {
                parentChars.Remove(currentItem.Letter);
            }
        }
    }

    private void DecrementCount(string value)
    {
        Dictionary<char, Item> currentChars = _rootChars;
        Item currentItem = null;

        foreach (char c in value)
        {
            currentItem = currentChars[c];
            currentItem.Total--;
            currentChars = currentItem.Items;
        }
    }

    public void Clear()
    {
        _rootChars.Clear();
    }

    public int GetValuesByPrefixCount(string prefix)
    {
        int valuescount = 0;

        int level = 0;
        Dictionary<char, Item> currentChars = _rootChars;
        Item currentItem = null;

        foreach (char c in prefix)
        {
            if (currentChars.ContainsKey(c))
            {
                currentItem = currentChars[c];
                currentChars = currentItem.Items;
            }
            else
            {
                return valuescount; // no matches found
            }
            level++;
        }

        valuescount = currentItem.Total;

        return valuescount;
    }

    public HashSet<string> GetValuesByPrefixFlattened(string prefix)
    {
        var results = GetValuesByPrefix(prefix);
        return new HashSet<string>(results.SelectMany(x => x));
    }

    public List<HashSet<string>> GetValuesByPrefix(string prefix)
    {
        var values = new List<HashSet<string>>();

        int level = 0;
        Dictionary<char, Item> currentChars = _rootChars;
        Item currentItem = null;

        foreach (char c in prefix)
        {
            if (currentChars.ContainsKey(c))
            {
                currentItem = currentChars[c];
                currentChars = currentItem.Items;
            }
            else
            {
                return values; // no matches found
            }
            level++;
        }

        ExtractValues(values, currentItem);

        return values;
    }

    public void ExtractValues(List<HashSet<string>> values, Item item)
    {
        foreach (Item subitem in item.Items.Values)
        {
            ExtractValues(values, subitem);
        }

        values.Add(item.Values);
    }

    public class Item
    {
        public int Level { get; set; }
        public char Letter { get; set; }
        public int Total { get; set; }
        public HashSet<string> Values { get; set; }
        public Dictionary<char, Item> Items { get; set; }

        public Item()
        {
            Values = new HashSet<string>();
            Items = new Dictionary<char, Item>();
        }
    }
}

Aquí está la prueba de unidad y el código de ejemplo de cómo usar esta clase.

using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;

    [TestClass]
    public class StringIndexTest
    {
        [TestMethod]
        public void AddAndSearchValues()
        {

            var si = new StringIndex();

            si.Add("abcdef", "1");
            si.Add("abcdeff", "2");
            si.Add("abcdeffg", "3");
            si.Add("bcdef", "4");
            si.Add("bcdefg", "5");
            si.Add("cdefg", "6");
            si.Add("cdefgh", "7");

            var output = si.GetValuesByPrefixFlattened("abc");

            Assert.IsTrue(output.Contains("1") && output.Contains("2") && output.Contains("3"));
        }

        [TestMethod]
        public void RemoveAndSearch()
        {

            var si = new StringIndex();

            si.Add("abcdef", "1");
            si.Add("abcdeff", "2");
            si.Add("abcdeffg", "3");
            si.Add("bcdef", "4");
            si.Add("bcdefg", "5");
            si.Add("cdefg", "6");
            si.Add("cdefgh", "7");

            si.Remove("abcdef", "1");

            var output = si.GetValuesByPrefixFlattened("abc");

            Assert.IsTrue(!output.Contains("1") && output.Contains("2") && output.Contains("3"));
        }

        [TestMethod]
        public void Clear()
        {

            var si = new StringIndex();

            si.Add("abcdef", "1");
            si.Add("abcdeff", "2");
            si.Add("abcdeffg", "3");
            si.Add("bcdef", "4");
            si.Add("bcdefg", "5");
            si.Add("cdefg", "6");
            si.Add("cdefgh", "7");

            si.Clear();
            var output = si.GetValuesByPrefix("abc");

            Assert.IsTrue(output.Count == 0);
        }

        [TestMethod]
        public void AddAndSearchValuesCount()
        {

            var si = new StringIndex();

            si.Add("abcdef", "1");
            si.Add("abcdeff", "2");
            si.Add("abcdeffg", "3");
            si.Add("bcdef", "4");
            si.Add("bcdefg", "5");
            si.Add("cdefg", "6");
            si.Add("cdefgh", "7");

            si.Remove("cdefgh", "7");

            var output1 = si.GetValuesByPrefixCount("abc");
            var output2 = si.GetValuesByPrefixCount("b");
            var output3 = si.GetValuesByPrefixCount("bc");
            var output4 = si.GetValuesByPrefixCount("ca");

            Assert.IsTrue(output1 == 3 && output2 == 2 && output3 == 2 && output4 == 0);
        }
    }

Cualquier sugerencia sobre cómo mejorar esta clase es bienvenida :)

Answer 2

Código de trabajo basado en la solución de Sam Holder (tenga en cuenta que da h: / a / not h: / a como la subcadena inicial común más larga en la pregunta):

using System;

namespace CommonPrefix
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(CommonPrefix(new[] { "h:/a/b/c", "h:/a/b/d", "h:/a/b/e", "h:/a/c" })); // "h:/a/"
            Console.WriteLine(CommonPrefix(new[] { "abc", "abc" })); // "abc"
            Console.WriteLine(CommonPrefix(new[] { "abc" })); // "abc"
            Console.WriteLine(CommonPrefix(new string[] { })); // ""
            Console.WriteLine(CommonPrefix(new[] { "a", "abc" })); // "a"
            Console.WriteLine(CommonPrefix(new[] { "abc", "a" })); // "a"

            Console.ReadKey();
        }

        private static string CommonPrefix(string[] ss)
        {
            if (ss.Length == 0)
            {
                return "";
            }

            if (ss.Length == 1)
            {
                return ss[0];
            }

            int prefixLength = 0;

            foreach (char c in ss[0])
            {
                foreach (string s in ss)
                {
                    if (s.Length <= prefixLength || s[prefixLength] != c)
                    {
                        return ss[0].Substring(0, prefixLength);
                    }
                }
                prefixLength++;
            }

            return ss[0]; // all strings identical up to length of ss[0]
        }
    }
}

Answer 3

Escribí esta extensión ICollection para encontrar el Uri de base común más largo de una colección de direcciones web.

Como solo verifica la colección de cadenas en cada barra, será un poco más rápido que una rutina de prefijo genérico (¡sin contar mi algoritmo ineficiente!). Es detallado, pero fácil de seguir ... mi tipo de código favorito ;-)

Ignora ''http: //'' y ''https: //'', así como el caso.

    /// <summary>
    /// Resolves a common base Uri from a list of Uri strings. Ignores case. Includes the last slash
    /// </summary>
    /// <param name="collectionOfUriStrings"></param>
    /// <returns>Common root in lowercase</returns>
    public static string GetCommonUri(this ICollection<string> collectionOfUriStrings)
    {
        //Check that collection contains entries
        if (!collectionOfUriStrings.Any())
            return string.Empty;
        //Check that the first is no zero length
        var firstUri = collectionOfUriStrings.FirstOrDefault();
        if(string.IsNullOrEmpty(firstUri))
            return string.Empty;

        //set starting position to be passed ''://''
        int previousSlashPos = firstUri.IndexOf("://", StringComparison.OrdinalIgnoreCase) + 2;
        int minPos = previousSlashPos + 1; //results return must have a slash after this initial position
        int nextSlashPos = firstUri.IndexOf("/", previousSlashPos + 1, StringComparison.OrdinalIgnoreCase);
        //check if any slashes
        if (nextSlashPos == -1)
            return string.Empty;

        do
        {               
            string common = firstUri.Substring(0, nextSlashPos + 1);
            //check against whole collection
            foreach (var collectionOfUriString in collectionOfUriStrings)
            {
                if (!collectionOfUriString.StartsWith(common, StringComparison.OrdinalIgnoreCase))
                {
                    //return as soon as a mismatch is found
                    return previousSlashPos > minPos ? firstUri.Substring(0, previousSlashPos + 1).ToLower() : string.Empty ;
                }
            }
            previousSlashPos = nextSlashPos;                
            nextSlashPos = firstUri.IndexOf("/", previousSlashPos + 1, StringComparison.OrdinalIgnoreCase);
        } while (nextSlashPos != -1);

        return previousSlashPos > minPos ? firstUri.Substring(0, previousSlashPos + 1).ToLower() : string.Empty;
    } 

Answer 4

Este es el problema de subcadena común más largo (aunque es un caso ligeramente especializado ya que parece que solo le importa el prefijo). No existe una implementación de la biblioteca del algoritmo en la plataforma .NET a la que pueda llamar directamente, pero el artículo aquí enlazado está repleto de pasos sobre cómo lo haría usted mismo.

Answer 5

Mi enfoque sería, tomar la primera cadena. Obtenga letra por letra mientras que todas las demás cadenas tienen la misma letra en la misma posición de índice y deténgase si no hay coincidencia. Elimina el último carácter si es un separador.

var str_array = new string[]{"h:/a/b/c",
         "h:/a/b/d",
         "h:/a/b/e",
         "h:/a/c"};
var separator = ''/'';

// get longest common prefix (optinally use ToLowerInvariant)
var ret = str_array.Any() 
    ? str_array.First().TakeWhile((s,i) => 
         str_array.All(e => 
            Char.ToLowerInvariant(s) == Char.ToLowerInvariant(e.Skip(i).Take(1).SingleOrDefault()))) 
    : String.Empty;

// remove last character if it''s a separator (optional)
if (ret.LastOrDefault() == separator) 
    ret = ret.Take(ret.Count() -1);

string prefix = new String(ret.ToArray());

Answer 6

Necesitaba buscar el prefijo común más largo en cadenas diferentes. Se me ocurrio:

private string FindCommonPrefix(List<string> list)
{
    List<string> prefixes = null;
    for (int len = 1; ; ++len)
    {
        var x = list.Where(s => s.Length >= len)
                    .GroupBy(c => c.Substring(0,len))
                    .Where(grp => grp.Count() > 1)
                    .Select(grp => grp.Key)
                    .ToList();

        if (!x.Any())
        {
            break;
        }
        //  Copy last list
        prefixes = new List<string>(x);
    }

    return prefixes == null ? string.Empty : prefixes.First();
}

Si hay más de un prefijo con la misma longitud, devuelve arbitrariamente el primero encontrado. También es sensible a mayúsculas y minúsculas. ¡Ambos puntos pueden ser abordados por el lector!

Answer 7

Quería un prefijo de cadena común, excepto que quería incluir cualquier carácter (como /) y no quería algo que funcionara o que me gustara solo algo que puedo leer con las pruebas. Así que tengo esto: https://github.com/fschwiet/DreamNJasmine/commit/ad802611ceacc673f2d03c30f7c8199f552b586f

public class CommonStringPrefix
{
    public static string Of(IEnumerable<string> strings)
    {
        var commonPrefix = strings.FirstOrDefault() ?? "";

        foreach(var s in strings)
        {
            var potentialMatchLength = Math.Min(s.Length, commonPrefix.Length);

            if (potentialMatchLength < commonPrefix.Length)
                commonPrefix = commonPrefix.Substring(0, potentialMatchLength);

            for(var i = 0; i < potentialMatchLength; i++)
            {
                if (s[i] != commonPrefix[i])
                {
                    commonPrefix = commonPrefix.Substring(0, i);
                    break;
                }
            }
        }

        return commonPrefix;
    }
}

Answer 8

Simplemente recorra los caracteres de la secuencia más corta y compare cada carácter con el carácter en la misma posición en las otras cadenas. Mientras todos los partidos continúan. Tan pronto como no coincida, la cadena hasta la posición actual -1 es la respuesta.

Algo así como (pseudo código)

int count=0;
foreach(char c in shortestString)
{
    foreach(string s in otherStrings)
    {
        if (s[count]!=c)
        {
             return shortestString.SubString(0,count-1); //need to check count is not 0 
        }
    }
    count+=1;
 }
 return shortestString;

Answer 9

Una solución corta de LINQy mía.

var samples = new[] { "h:/a/b/c", "h:/a/b/d", "h:/a/b/e", "h:/a/e" };

var commonPrefix = new string(
    samples.First().Substring(0, samples.Min(s => s.Length))
    .TakeWhile((c, i) => samples.All(s => s[i] == c)).ToArray());

Answer 10

string[] xs = new[] { "h:/a/b/c", "h:/a/b/d", "h:/a/b/e", "h:/a/c" };

string x = string.Join("/", xs.Select(s => s.Split(''/'').AsEnumerable())
                              .Transpose()
                              .TakeWhile(s => s.All(d => d == s.First()))
                              .Select(s => s.First()));

con

public static IEnumerable<IEnumerable<T>> Transpose<T>(
    this IEnumerable<IEnumerable<T>> source)
{
    var enumerators = source.Select(e => e.GetEnumerator()).ToArray();
    try
    {
        while (enumerators.All(e => e.MoveNext()))
        {
            yield return enumerators.Select(e => e.Current).ToArray();
        }
    }
    finally
    {
        Array.ForEach(enumerators, e => e.Dispose());
    }
}