Алгоритм хеширования

Slavik12

Slavik12
Статус: Offline
Реєстрація: 16.04.2009
Повідом.: 76
Алгоритм хеширования

Надо реализовать алгоритм хеширования, работает так:
all_text = "QWERTY"
required_text = "QW"
сначала хешируем QW, т.к. required_text.Length = 2, потом WE, потом ER...
из этого должен получится набор чисел.

Код: 
public string Hash_Text(string all_text, string required_text)
        {
            StringBuilder temp0 = new StringBuilder();
            StringBuilder u = new StringBuilder();
            char[] char_all_text = all_text.ToCharArray();
            char[] char_required_text = required_text.ToCharArray();
            
 
                for (int i = 0; i < Math.Round(((double)all_text.Length / (double)required_text.Length)); i++)
                {
                    
                    while (u.Length<=char_required_text.Length)
                    {
                        u.Append(Convert.ToInt32(char_all_text[i]));
                        if (i<char_all_text.Length)
                        {
                            i++;
                        }
                        
                    } //System.Math.Abs
                    temp0.Append((Convert.ToInt32(u.ToString()))%100);
                    u.Remove(0, u.Length);
                }
                return temp0.ToString();
        }



пробовал так:


Код: 
public string Hash_Text(string all_text, string required_text)
        {
            StringBuilder temp0 = new StringBuilder();
            StringBuilder u = new StringBuilder();
            char[] char_all_text = all_text.ToCharArray();
            char[] char_required_text = required_text.ToCharArray();
            
 
                for (int i = 0; i < all_text.Length; i++)
                {
                    for (int j = 0; j < char_required_text.Length; j++)
                    {
                        u.Append(Convert.ToInt32(char_all_text[j]));
                    }
                    temp0.Append(((Convert.ToInt32(u.ToString()))%29).ToString());
                    u.Remove(0, u.Length);
                    
 
                    char_all_text = char_all_text.ToString().Remove(0, 1).ToCharArray();
                }
                return temp0.ToString();
 
и что?
 
Видимо самым простым способом закончить эти мучения будет выкладывание готовой реализации:

Код: 
using System;

namespace CSharpTestApp
{
	class Program
	{
		class Hasher
		{
			private readonly int _hashBase;
			private int _lastLen = -1;
			private long _cachedHashBasePow = 0;

			public Hasher()
				: this(31)
			{
			}

			public Hasher(int hashBase)
			{
				_hashBase = hashBase;
			}

			private static long CharToLong(char c)
			{
				return c - ' ';	//space (32) is the first "good" char in ASCII
			}

			public long CalcHash(string str, int start, int len)
			{
				long hash = 0;
				long mul = 1;
				for (int i = 0; i < len; i++)
				{
					char c = str[start + i];
					hash += CharToLong(c) * mul;
					mul *= _hashBase;
				}
				_lastLen = len;
				_cachedHashBasePow = mul / _hashBase;

				return hash;
			}



			private long GetHashBasePow(int len)
			{
				//small optimization
				if (_lastLen != len)
				{
					_cachedHashBasePow = 1;
					for (int i = 0; i < len - 1; i++)
					{
						_cachedHashBasePow *= _hashBase;
					}
					_lastLen = len;
				}
				return _cachedHashBasePow;
			}

			public long UpdateHash(long oldHash, string str, int newStart, int len)
			{
				char oldC = str[newStart - 1];
				char newC = str[newStart + len - 1];
				long newHash = (oldHash - CharToLong(oldC)) / _hashBase + CharToLong(newC) * GetHashBasePow(len);
				return newHash;
			}
		}

		static int FindSubstringsCnt(string fullText, string pattern, Hasher hasher)
		{
			if (fullText == null) throw new ArgumentNullException("fullText");
			if (pattern == null) throw new ArgumentNullException("pattern");
			if (pattern.Length == 0) throw new ArgumentException("pattern is empty", "pattern");

			if (fullText.Length < pattern.Length) return 0;
			if (fullText.Length == pattern.Length) return (fullText.Equals(pattern)) ? 1 : 0;

			long patternHash = hasher.CalcHash(pattern, 0, pattern.Length);
			long curHash = hasher.CalcHash(fullText, 0, pattern.Length);
			int cnt = 0;
			if (curHash == patternHash)
			{
				if (fullText.StartsWith(pattern)) cnt++;
			}
			for (int i = 1; i < fullText.Length - pattern.Length; i++)
			{
				curHash = hasher.UpdateHash(curHash, fullText, i, pattern.Length);
				if (curHash != patternHash) continue;
				if (pattern.Equals(fullText.Substring(i, pattern.Length))) cnt++;
			}

			return cnt;
		}

		static void Main(string[] args)
		{
			const string fullText = "0AbcAbcdAbcdeAbcdef";
			const string pattern = "Abcd";
			int cnt = FindSubstringsCnt(fullText, pattern, new Hasher());
			Console.WriteLine("'{1}' was found {2} time(s) in \r\n'{0}'", fullText, pattern, cnt);
		}
	}
}
 
balkauser сказав(ла):
Видимо самым простым способом закончить эти мучения будет выкладывание готовой реализации:

Код: 
using System;

namespace CSharpTestApp
{
	class Program
	{
		class Hasher
		{
			private readonly int _hashBase;
			private int _lastLen = -1;
			private long _cachedHashBasePow = 0;

			public Hasher()
				: this(31)
			{
			}

			public Hasher(int hashBase)
			{
				_hashBase = hashBase;
			}

			private static long CharToLong(char c)
			{
				return c - ' ';	//space (32) is the first "good" char in ASCII
			}

			public long CalcHash(string str, int start, int len)
			{
				long hash = 0;
				long mul = 1;
				for (int i = 0; i < len; i++)
				{
					char c = str[start + i];
					hash += CharToLong(c) * mul;
					mul *= _hashBase;
				}
				_lastLen = len;
				_cachedHashBasePow = mul / _hashBase;

				return hash;
			}



			private long GetHashBasePow(int len)
			{
				//small optimization
				if (_lastLen != len)
				{
					_cachedHashBasePow = 1;
					for (int i = 0; i < len - 1; i++)
					{
						_cachedHashBasePow *= _hashBase;
					}
					_lastLen = len;
				}
				return _cachedHashBasePow;
			}

			public long UpdateHash(long oldHash, string str, int newStart, int len)
			{
				char oldC = str[newStart - 1];
				char newC = str[newStart + len - 1];
				long newHash = (oldHash - CharToLong(oldC)) / _hashBase + CharToLong(newC) * GetHashBasePow(len);
				return newHash;
			}
		}

		static int FindSubstringsCnt(string fullText, string pattern, Hasher hasher)
		{
			if (fullText == null) throw new ArgumentNullException("fullText");
			if (pattern == null) throw new ArgumentNullException("pattern");
			if (pattern.Length == 0) throw new ArgumentException("pattern is empty", "pattern");

			if (fullText.Length < pattern.Length) return 0;
			if (fullText.Length == pattern.Length) return (fullText.Equals(pattern)) ? 1 : 0;

			long patternHash = hasher.CalcHash(pattern, 0, pattern.Length);
			long curHash = hasher.CalcHash(fullText, 0, pattern.Length);
			int cnt = 0;
			if (curHash == patternHash)
			{
				if (fullText.StartsWith(pattern)) cnt++;
			}
			for (int i = 1; i < fullText.Length - pattern.Length; i++)
			{
				curHash = hasher.UpdateHash(curHash, fullText, i, pattern.Length);
				if (curHash != patternHash) continue;
				if (pattern.Equals(fullText.Substring(i, pattern.Length))) cnt++;
			}

			return cnt;
		}

		static void Main(string[] args)
		{
			const string fullText = "0AbcAbcdAbcdeAbcdef";
			const string pattern = "Abcd";
			int cnt = FindSubstringsCnt(fullText, pattern, new Hasher());
			Console.WriteLine("'{1}' was found {2} time(s) in \r\n'{0}'", fullText, pattern, cnt);
		}
	}
}
Натисніть, щоб розгорнути...

Спасибо за код, можете разжевать его пожалуйста:
Что хранят следующие обьекты?
private readonly int _hashBase;
private long _cachedHashBasePow = 0;
 
Slavik12 сказав(ла):
Что хранят следующие обьекты?
private readonly int _hashBase;
private long _cachedHashBasePow = 0;
Натисніть, щоб розгорнути...

Вернёмся к алгоритму Карпа-Рабина. В его основе лежит хэширующая функция. При этом ключевым для эффективности алгоритма является правильный её выбор. А именно, мы должны уметь быстро вычислять её на основе прошлых значений и изменений хэшируемой (под-)строки. Если нам каждый раз для вычисления значения хэша нужно пробегать всю (под-)строку, то это полностью убивает весь алгоритм: тогда эффективнее уже сразу сравнивать подстроку с шаблоном.
Одной из простых таких функций является функция такого вида: выбираем основание (_hashBase) и считаем сумму
Код: 
код_буквы[0]*1+код_буквы[1]*основание + код_буквы[2]*основание^2 + ... + код_буквы[N]*основание^N
Тогда если у нас есть A(i,n) - хэш для подстроки длины n начиная с позиции i и нам нужно получить хэш для следующей подстроки, мы можем посчитать её так:
Код: 
A(i+1,n) = A(i+1, n-1) + код_добавляемой_буквы*основание^(n-1)
С другой стороны
Код: 
A(i+1,n-1) = (A(i, n)-код_первой_буквы)/основание
Или объединяя
Код: 
A(i+1,n) = (A(i, n)-код_убираемой_буквы)/основание + код_добавляемой_буквы*основание^(n-1)

Класс Hasher и инкапсулирует соответствующую логику. При этом важно, что возвращаемый тип всего лишь long - т.е. 64 битное число (да ещё и со знаком), что не так уж и много. Следовательно при большом значении основания и длинном шаблоне уже даже само основание^(n-1) может легко переполнить это значение, что приведёт к неправильному вычислению по итеративной формуле (деление будет неправильным). (Для текущего значения по умолчанию 31 критической является длина шаблона 8). Поэтому значение основания сделано переменным. В самом крайнем случае (длинный шаблон) можно использовать значения 1 или (для извращенцев) -1, для которых переполнение не важно, но которые порождают множество коллизий.

Дальше, можно заметить, что при итеративном вычислении часто используется величина основание^(n-1). При этом n - постоянно и равно длине шаблона. Соответственно можно немного схитрить и посчитать его всего лишь 1 раз, а в дальнейшем использовать кэшированное (пред-вычисленное) значение. _cachedHashBasePow и _lastLen хранят пред-вычисленную степень и длину шаблона, для которой она была вычислена.
 
balkauser сказав(ла):
Вернёмся к алгоритму Карпа-Рабина. В его основе лежит хэширующая функция. При этом ключевым для эффективности алгоритма является правильный её выбор. А именно, мы должны уметь быстро вычислять её на основе прошлых значений и изменений хэшируемой (под-)строки. Если нам каждый раз для вычисления значения хэша нужно пробегать всю (под-)строку, то это полностью убивает весь алгоритм: тогда эффективнее уже сразу сравнивать подстроку с шаблоном.
Одной из простых таких функций является функция такого вида: выбираем основание (_hashBase) и считаем сумму
Код: 
код_буквы[0]*1+код_буквы[1]*основание + код_буквы[2]*основание^2 + ... + код_буквы[N]*основание^N
Тогда если у нас есть A(i,n) - хэш для подстроки длины n начиная с позиции i и нам нужно получить хэш для следующей подстроки, мы можем посчитать её так:
Код: 
A(i+1,n) = A(i+1, n-1) + код_добавляемой_буквы*основание^(n-1)
С другой стороны
Код: 
A(i+1,n-1) = (A(i, n)-код_первой_буквы)/основание
Или объединяя
Код: 
A(i+1,n) = (A(i, n)-код_убираемой_буквы)/основание + код_добавляемой_буквы*основание^(n-1)

Класс Hasher и инкапсулирует соответствующую логику. При этом важно, что возвращаемый тип всего лишь long - т.е. 64 битное число (да ещё и со знаком), что не так уж и много. Следовательно при большом значении основания и длинном шаблоне уже даже само основание^(n-1) может легко переполнить это значение, что приведёт к неправильному вычислению по итеративной формуле (деление будет неправильным). (Для текущего значения по умолчанию 31 критической является длина шаблона 8). Поэтому значение основания сделано переменным. В самом крайнем случае (длинный шаблон) можно использовать значения 1 или (для извращенцев) -1, для которых переполнение не важно, но которые порождают множество коллизий.

Дальше, можно заметить, что при итеративном вычислении часто используется величина основание^(n-1). При этом n - постоянно и равно длине шаблона. Соответственно можно немного схитрить и посчитать его всего лишь 1 раз, а в дальнейшем использовать кэшированное (пред-вычисленное) значение. _cachedHashBasePow и _lastLen хранят пред-вычисленную степень и длину шаблона, для которой она была вычислена.
Натисніть, щоб розгорнути...

Спасибо! Всё по полочкам разложили!
 
Ви повинні увійти або зареєструватися, щоб відповісти.
Назад
Зверху Знизу