Главная → Беседка → Блоги → Блог блондинки-программистки
Julia Aipkina

			

				
Расстояние Левенштейна. Что это?


				28.11.2008 12:19:59
			

			

				                         Да, вот такая беда: я до недавнего времени не знала, что такое Левенштейн.



Расстояние Левенштейна - это минимальное количество вставок, замен и удалений символов, необходимое для преобразования из одной строки в другую.



Например, "день" превращаем в "ночь". Человек - сам себе компьютер. Посчитал, что расстояние Левеештейна=3. Но что в это время делает человеческий мозг?

Проверяет схожесть строк. Она одна - четвертая буква - "ь".

Значит, "замен" будет 3.

1) "д" на "н"

2) "е" на "о"

3) "н" на "ч"



Минимальная границы расстояния Левенштейна - разность длины сравниваемых строк. Если нам "м" надо превратить в "мама", например.



Ну а максимальное расстояние Левенштейна - длина самой длинной строки. Если мы слово "гексоцианоферрат" хотим превратить в "я", то мы сделаем как раз-таки 11 операций.

                         			

			

				
 

															

	

	

	

		



	
	
			

		
		

			
				

				
Написать комментарий

		

		



                    

                                    

            

        
    
        

            

                

                    
Конкурсы и олимпиады

	

			«EVA 2008 - Студент»

		12.11.2008
		
 Оргкомитет XI Международной конференции «EVA 2008 Москва» приглашает вас принять участие в студенческом научно-проектном конкурсе-семинаре «EVA 2008-Студент», который будет проходить 3-4 декабря на базе ВГБИЛ и МГУКИ в рамках международной конференции «EVA 2008 Москва».

	

	

	
 
		XI Конкурс для старшеклассников «Издательская деятельность в школе»

		
		
Городской конкурс для старшеклассников «Издательская деятельность в школе» проводится в Санкт-Петербурге с 1995 года. Каждый год участникам предлагается раскрыть тему конкурса, используя различные формы представления информации: журнал, газета, дайджест, плакат, сайт.

	

                

                

                    
Стипендии и гранты

	

			Кипрский колледж университетского типа Интерколледж

		
		
Кипрский колледж университетского типа Интерколледж выделяет гранты, покрывающие 50% стоимости для обучения в Лимассоле по двухлетним программам и четырехлетней программе на степень бакалавра.

	

	

	
 
		Фонд имени В.И. Вернадского

		
		
Стипендия им. В.И. Вернадского учреждена с целью поощрения учебной и научной деятельности студентов очного обучения высших учебных заведений. Стипендии назначаются на конкурсной основе как студентам российских вузов, так и зарубежным студентам. Конкурс среди иностранных студентов проводит московская конкурсная комиссия.