DIỄN ĐÀN hochanh.net.vn
Cảm ơn bạn đã quan tâm đến học hành và tham gia diễn đàn hochanh.net.vn
Tìm kiếm
 
 

Display results as :
 


Rechercher Advanced Search

Gallery


Đăng nhập với tên thanhvien VIP

28/8/2010, 21:37 by ABC

BẠN CÓ THỂ ĐĂNG KÝ RỒI ĐĂNG NHẬP
HOẶC ĐĂNG NHẬP
VỚI TÊN thanhvienvip
hoặc thanhvien 1
hoặc thanhvien 2
hoặc thanhvien 3

và mật khẩu là 1234567890

để không có dòng quảng cáo trên.

Comments: 0

HỌC ĐI ĐÔI VỚI HÀNH ?

28/4/2010, 22:40 by Admin

Học đi đôi với hành


“ trăm hay không bằng tay quen”. người lao động xưa đã từng quan niệm rằng lí thuyết hay không bằng thức hành giỏi. điều đó cho thấy người xưa đã đề cao vai trò của thức hành . trong khi đó những kẻ học thức chỉ biết chữ nghĩa thánh hiền, theo lối học từ chương sáo mòn cũ kĩ. …

[ Full reading ]

Comments: 2

Poll
Keywords


UTF-8 cho cơ sở dữ liệu MySQL

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

UTF-8 cho cơ sở dữ liệu MySQL

Bài gửi by học lóm on 15/6/2010, 22:11

UTF-8 cho cơ sở dữ liệu MySQL

Khi làm web bằng PHP và MySQL thì vấn đề xử lý tiếng Việt rất được hay gặp. Đôi khi nó gây rắc rối cho người làm web ở các thao tác như: sao lưu và phục hồi cơ sở dữ liệu, tạo table mới, lưu trữ và lấy dữ liệu từ cơ sở dữ liệu và hiển thị đúng, ... Bản...

Khi làm web bằng PHP và MySQL thì vấn đề xử lý tiếng Việt rất được hay gặp. Đôi khi nó gây rắc rối cho người làm web ở các thao tác như: sao lưu và phục hồi cơ sở dữ liệu, tạo table mới, lưu trữ và lấy dữ liệu từ cơ sở dữ liệu và hiển thị đúng, ... Bản thân tôi cũng đã gặp vài lần rắc rối với tiếng Việt trong việc xử lý dữ liệu, nên viết bài này tổng hợp một số cái đã trải qua để ghi nhớ cho sau này.

Tìm hiểu về charset và collation

Chúng ta tạm hiểu charset (viết đầy đủ là character set) là tập hợp các ký tự và mã hóa tương ứng của chúng, còn collation là quy tắc để so sánh các ký tự nằm trong 1 charset. Trang chủ của MySQL có ví dụ khá rõ ràng để giải thích hai khái niệm này.

Thông thường (ở đây chúng ta chỉ nói đến MySQL) thì đối với mỗi charset có một collation mặc định đi kèm theo nó, Ví dụ: latin1 <=> latin1_swedish_ci, utf8 <=> utf8_general_ci, ...

Các tham số của charset và collation

Đối với MySQL, thì charset và collation hiện diện ở những vị trí sau:

- Phía client: dữ liệu của phía client trước tiên cần phải mã hóa theo một charset nào đó, thông thường chúng ta dùng utf-8. Giá trị của charset này được MySQL lưu giữ trong tham số hệ thống character_set_client.

- Phía server: charset và collation được dùng để mã hóa dữ liệu lưu trong hệ thống, các tham số tương ứng là character_set_server và collation_server. Ngoài ra, khi server trả dữ liệu trở lại về cho client thì chúng cũng cần phải có charset tương ứng, và tham số ứng với nó là character_set_results.

- Hơn thế nữa, nằm trung gian giữa client và server là 1 kết nối (connection) được tạo ra khi client gửi yêu cầu tới server (hoặc server trả kết quả về cho client). Connection này cũng yêu cầu phải có charset và collation, chúng được lưu trong các tham số hệ thống character_set_connection và collation_connection.

Như vậy, tổng hợp lại có cả thảy 6 tham số lưu giữ những thuộc tính về charset và collation:

character_set_client
character_set_server
collation_server
character_set_results
character_set_connection
collation_connection


Từ đây chúng ta suy ra để server và client "có tiếng nói chung", Ví dụ như chúng ta muốn ghi vào table dữ liệu ở đúng dạng utf8 mà chúng ta có, thì các tham số trên phải được thiết lập cùng một nhóm với nhau utf8 và utf8_general_ci.

Cách thiết lập charset và collation

Đối với người quản trị server, có quyền thao tác trên dòng lệnh với mysql thì có thể thiết lập chúng bằng câu lệnh sau:



  1. SET character_set_client = utf8;
  2. SET character_set_server = utf8;
  3. SET collation_server = utf8_general_ci;
  4. ...
  5. (các lệnh sau tương tự)


SET character_set_client = utf8;
SET character_set_server = utf8;
SET collation_server = utf8_general_ci;
...
(các lệnh sau tương tự)

(ở đây lấy ví dụ là utf8, đối với các charset và collation khác làm tương tự)

Tuy vậy, như thế khá dài dòng, MySQL có cung cấp cho chúng ta câu lệnh ngắn hơn như sau:

  1. SET NAMES utf8 [COLLATE utf8_general_ci]

SET NAMES utf8 [COLLATE utf8_general_ci]

Phần trong dấu ngoặc vuông [] là không bắt buộc, nghĩa là nếu không có phần đó, collation mặc định tương ứng với charset đó sẽ được dùng. Chỗ này lưu ý là với mỗi charset có thể có nhiều collation.

Câu lệnh trên không tương ứng với hoàn toàn 6 lệnh ban đầu, mà nó chỉ tương đương với 3 lệnh sau:

  1. SET character_set_client = utf8;
  2. SET character_set_results = utf8;
  3. SET character_set_connection = utf8;

SET character_set_client = utf8;
SET character_set_results = utf8;
SET character_set_connection = utf8;

Ở đây cũng lưu ý là các collation sẽ được thiết lập (mặc định) tương ứng với các charset đó. Tuy vậy, các bạn có thể thấy là vẫn thiếu lệnh thiết lập cho character_set_server.

Ngoài ra, MySQL còn cung cấp một lệnh rút ngắn khác, tương tư như SET NAMES ở trên, đó là:

  1. SET CHARACTER SET utf8;

SET CHARACTER SET utf8;

Lệnh này cơ bản giống lệnh trên, tuy vậy, nó thiết lập charset và collation của connection (2 tham số character_set_connection, collation_connection) giống với charset và collation của database (2 tham số character_set_database, collation_database), nó tương đương với:

  1. SET character_set_client = utf8;
  2. SET character_set_results = utf8;
  3. SET collation_connection = @@collation_database;

SET character_set_client = utf8;
SET character_set_results = utf8;
SET collation_connection = @@collation_database;

Đối với lập trình viên, khi bạn không có quyền thao tác trên dòng lệnh của mysql, thì có thể dùng câu lệnh PHP sau:view plaincopy to clipboardprint?



  1. mysql_query('SET NAMES utf8 COLLATE utf8_general_ci');

mysql_query('SET NAMES utf8 COLLATE utf8_general_ci');

hoặcview plaincopy to clipboardprint?



  1. mysql_query('SET CHARACTER SET utf8');

mysql_query('SET CHARACTER SET utf8');

Khi tôi thử nghiệm dùng các lệnh trên để thiết lập cho các kết nối tới cơ sở dữ liệu thì lệnh SET NAMES hoạt động tốt hơn lệnh SET CHARACTER SET. Có thể là do MySQL để kiểu charset và collation mặc định cho database là latin1, mà chúng ta thì cần utf8.

Như thế, sau khi chạy lệnh SET NAMES (thường thì chạy theo cách 2 trong PHP) thì bạn có thể yên tâm tạo các truy vấn tới CSDL. Dữ liệu được ghi vào CSDL lúc này bạn có thể đọc được tiếng Việt luôn khi xem bằng PHPMyAdmin.

Những gì trình bày ở trên nên được áp dụng khi bạn tự viết một ứng dụng web mới. Đối với các ứng dụng đã có thì cần lưu ý xem nó có ảnh hưởng tới những gì đã có hay không (Ví dụ trong trường hợp dữ liệu của bạn lưu trữ không phải với collation utf8_general_ci chẳng hạn).

Một vài rắc rối khác

Không phải tất cả đều đúng cho mọi phiên bản của MySQL. Những điều trên được áp dụng cho MySQL version 5.0 trở lên. Từ bản 5.0, MySQL đã hỗ trợ tốt hơn cho đa ngôn ngữ. Tuy vậy, nếu bạn đã từng dùng MySQL 4.x thì vấn đề trở nên rắc rối hơn hẳn.

Tôi cũng từng gặp vấn đề lỗi hiển thị tiếng Việt khi sao lưu và phục hồi bằng PHPMyAdmin giữa 1 host dùng MySQL 4.x và 1 host dùng MySQL 5.0. Lúc đó tôi phải làm thủ công, mở file CSDL đó ra, sửa tất cả các câu lệnh tạo bảng có CHARSET=latin1 thành CHARSET=utf8.

Tuy vậy, vấn đề sao lưu, phục hồi CSDL phụ thuộc vào charset và collation của nhiều thứ (ngoài những thứ trên), có thể kể ra đây gồm:

* charset, collation của database (và các table) ở host cũ
* charset của file SQL được sao lưu
* charset, collation của database ở host mới


Những thứ này liên quan trực tiếp đến database nhiều hơn (những thứ ở trên liên quan đến việc thao tác qua lại giữa ứng dụng web và MySQL). Kinh nghiệm của tôi cho thấy là để sao lưu và phục hồi được đúng thì nên thiết lập mọi tham số ở host mới giống hệt như host cũ. Ngoài ra thì với MySQL 4.x thì nên chuyển tất cả về latin1 (do nó chưa hỗ trợ tốt cho đa ngôn ngữ), còn với MySQL 5.x thì chuyển tất cả qua utf8.

Tham khảo: MySQL Documentation
Theo hontap.blogspot.com



[HaiPhong-Aptech st
avatar
học lóm
Thành viên trung thành
Thành viên trung thành

Tổng số bài gửi : 31
Điểm : 5449
Reputation : 0
Join date : 20/05/2010

Về Đầu Trang Go down

Re: UTF-8 cho cơ sở dữ liệu MySQL

Bài gửi by học lóm on 15/6/2010, 22:12

Lấy ngẫu nhiên records từ database

Đôi khi lập trình bạn vẫn thường gặp trường hợp phải xử lý vấn đề trên. Ví dụ: Lấy ngẫu nhiên danh sách câu hỏi sử dụng cho chương trình thi trắc nghiệm. Rất nhiều bạn chọn giải pháp là xử lý dữ liệu đã được lấy lên từ database. Bài viết này giới thiệu...

Đôi khi lập trình bạn vẫn thường gặp trường hợp phải xử lý vấn đề trên. Ví dụ: Lấy ngẫu nhiên danh sách câu hỏi sử dụng cho chương trình thi trắc nghiệm.

Rất nhiều bạn chọn giải pháp là xử lý dữ liệu đã được lấy lên từ database. Bài viết này giới thiệu các truy vấn các câu hỏi từ database:

Cách thứ nhất : dùng hàm Rand() hàm này sẽ trả về giá trị ngẫu nhiên > 0 và < 1.

Nhưng sử dụng hàm này có một bất lợi: khi bạn sử dụng trực tiếp hàm này trong câu lệnh truy vấn sẽ tạo ra một giá trị giống hệt nhau cho tất cả các records. Câu lệnh truy vấn sau :view plaincopy to clipboardprint?



  1. SELECT TOP 5 ProductName, RAND() as RandomValue FROM products ORDER BY 2
  2. SELECT RAND()

SELECT TOP 5 ProductName, RAND() as RandomValue FROM products ORDER BY 2
SELECT RAND()


Returns result 0.7154366573674853

sẽ cho ra kết quả:

ProductName RandomValue
Alice Mutton 0.80020779549998178
Aniseed Syrup 0.80020779549998178
Boston Crab Meat 0.80020779549998178
Camembert Pierrot 0.80020779549998178
Carnarvon Tigers 0.80020779549998178

Các giải quyết là viết một funciton sử dụng hàm rand này.

Cách thứ 2: Sử dụng hàm NewID(). Hàm này khắc phục vấn đề gặp ở trên với hàm rand(). Khi bạn sử dụng trực tiếp hàm NewID trong câu lệnh select thì kết quả sẽ tạo ra các giá trị ngẫu nhiên hoàn toàn khác nhau.


  1. SELECT TOP 5 productName FROM products ORDER BY NEWID()

SELECT TOP 5 productName FROM products ORDER BY NEWID()


kết quả chạy lần thứ nhất :

* Guaraná Fantástica
* Tunnbröd
* Ikura
* Filo Mix
* Genen Shouyu


Kết quả chạy lần thứ 2:

* Mozzarella di Giovanni
* Scottish Longbreads
* Gustaf's Knäckebröd
* Louisiana Fiery Hot Pepper Sauce
* Filo Mix






[HaiPhong-Aptech st]
avatar
học lóm
Thành viên trung thành
Thành viên trung thành

Tổng số bài gửi : 31
Điểm : 5449
Reputation : 0
Join date : 20/05/2010

Về Đầu Trang Go down

Re: UTF-8 cho cơ sở dữ liệu MySQL

Bài gửi by học lóm on 15/6/2010, 22:13

Cách tạo ảnh bảo mật trong PHP

Ảnh bảo mật là một loại ảnh được tạo tự động chứa các ký tự ngẫu nhiên dùng để ngăn chặn các chương trình tự động (spam bot) submit vào form bằng cách mã hoá chuỗi ký tự vào một ảnh và bắt người dùng phải gõ lại chuỗi ký tự đó. Hầu hết chúng ta đều đã...

Ảnh bảo mật là một loại ảnh được tạo tự động chứa các ký tự ngẫu nhiên dùng để ngăn chặn các chương trình tự động (spam bot) submit vào form bằng cách mã hoá chuỗi ký tự vào một ảnh và bắt người dùng phải gõ lại chuỗi ký tự đó.
Hầu hết chúng ta đều đã từng tạo email trong Yahoo nên những hình ảnh và công việc kiểu này hẳn là đã khá quen thuộc. Công việc này được thực hiện bởi thư viện GD chứa các hàm xử lý ảnh. Để sử dụng thư viện này với PHP trên localhost trong Windows, bạn cần nạp extension php_gd2.dll bằng cách xoá dấu ";" tại dòng ;extension=php_gd2.dll trong file php.ini (từ phiên bản PHP 4.3.2 trở đi, thư viện GD1 dc thay bởi GD2). Để biết thông tin về thư viện này cài đặt trên host, hãy tạo một file gd_info.php với nội dung:







Sau đó đặt vào thư mục gốc của server và chạy từ trình duyệt: http://hostname/gd_info.php

Có rất nhiều cách để tạo những ảnh như vậy. Đoạn mã PHP dưới đây sẽ tạo một hình ảnh như ở trên, chứa chuỗi ký tự ngẫu nhiên trên nền các chấm nhiễu cũng ngẫu nhiên. Các dòng trong cặp dấu /* */ là các dòng comment, sẽ được trình thông dịch của PHP bỏ qua. Nếu bạn có ý định sử dụng lại code này, vui lòng giữ lại đoạn comment đầu tiên.

view plaincopy to clipboardprint?



  1. session_start();

  2. /*
  3. * File: CaptchaSecurityImages.php
  4. * Author: Simon Jarvis
  5. * Copyright: 2006 Simon Jarvis
  6. * Date: 03/08/06
  7. * Updated: 07/02/07
  8. * Requirements: PHP 4/5 with GD and FreeType libraries
  9. * Link: http://www.white-hat-web-design.co.uk/articles/php-captcha.php
  10. *
  11. * This program is free software; you can redistribute it and/or
  12. * modify it under the terms of the GNU General Public License
  13. * as published by the Free Software Foundation; either version 2
  14. * of the License, or (at your option) any later version.
  15. *
  16. * This program is distributed in the hope that it will be useful,
  17. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  19. * GNU General Public License for more details:
  20. * http://www.gnu.org/licenses/gpl.html
  21. *
  22. */

  23. class CaptchaSecurityImages {

  24. var $font = 'monofont.ttf';

  25. function generateCode($characters) {
  26. /* list all possible characters, similar looking characters and vowels have been removed */
  27. $possible = '23456789bcdfghjkmnpqrstvwxyz';
  28. $code = '';
  29. $i = 0;
  30. while ($i < $characters) {
  31. $code .= substr($possible, mt_rand(0, strlen($possible)-1), 1);
  32. $i++;
  33. }
  34. return $code;
  35. }

  36. function CaptchaSecurityImages($width='120',$height='40',$characters='6') {
  37. $code = $this->generateCode($characters);
  38. /* font size will be 75% of the image height */
  39. $font_size = $height * 0.75;
  40. $image = @imagecreate($width, $height) or die('Cannot initialize new GD image stream');
  41. /* set the colours */
  42. $background_color = imagecolorallocate($image, 255, 255, 255);
  43. $text_color = imagecolorallocate($image, 20, 40, 100);
  44. $noise_color = imagecolorallocate($image, 100, 120, 180);
  45. /* generate random dots in background */
  46. for( $i=0; $i<($width*$height)/3; $i++ ) {
  47. imagefilledellipse($image, mt_rand(0,$width), mt_rand(0,$height), 1, 1, $noise_color);
  48. }
  49. /* generate random lines in background */
  50. for( $i=0; $i<($width*$height)/150; $i++ ) {
  51. imageline($image, mt_rand(0,$width), mt_rand(0,$height), mt_rand(0,$width), mt_rand(0,$height), $noise_color);
  52. }
  53. /* create textbox and add text */
  54. $textbox = imagettfbbox($font_size, 0, $this->font, $code) or die('Error in imagettfbbox function');
  55. $x = ($width - $textbox[4])/2;
  56. $y = ($height - $textbox[5])/2;
  57. imagettftext($image, $font_size, 0, $x, $y, $text_color, $this->font , $code) or die('Error in imagettftext function');
  58. /* output captcha image to browser */
  59. header('Content-Type: image/jpeg');
  60. imagejpeg($image);
  61. imagedestroy($image);
  62. $_SESSION['security_code'] = $code;
  63. }

  64. }

  65. $width = isset($_GET['width']) ? $_GET['width'] : '120';
  66. $height = isset($_GET['height']) ? $_GET['height'] : '40';
  67. $characters = isset($_GET['characters']) && $_GET['characters'] > 1 ? $_GET['characters'] : '6';

  68. $captcha = new CaptchaSecurityImages($width,$height,$characters);

  69. ?>

session_start();

/*
* File: CaptchaSecurityImages.php
* Author: Simon Jarvis
* Copyright: 2006 Simon Jarvis
* Date: 03/08/06
* Updated: 07/02/07
* Requirements: PHP 4/5 with GD and FreeType libraries
* Link: http://www.white-hat-web-design.co.uk/articles/php-captcha.php
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details:
* http://www.gnu.org/licenses/gpl.html
*
*/

class CaptchaSecurityImages {

var $font = 'monofont.ttf';

function generateCode($characters) {
/* list all possible characters, similar looking characters and vowels have been removed */
$possible = '23456789bcdfghjkmnpqrstvwxyz';
$code = '';
$i = 0;
while ($i < $characters) {
$code .= substr($possible, mt_rand(0, strlen($possible)-1), 1);
$i++;
}
return $code;
}

function CaptchaSecurityImages($width='120',$height='40',$characters='6') {
$code = $this->generateCode($characters);
/* font size will be 75% of the image height */
$font_size = $height * 0.75;
$image = @imagecreate($width, $height) or die('Cannot initialize new GD image stream');
/* set the colours */
$background_color = imagecolorallocate($image, 255, 255, 255);
$text_color = imagecolorallocate($image, 20, 40, 100);
$noise_color = imagecolorallocate($image, 100, 120, 180);
/* generate random dots in background */
for( $i=0; $i<($width*$height)/3; $i++ ) {
imagefilledellipse($image, mt_rand(0,$width), mt_rand(0,$height), 1, 1, $noise_color);
}
/* generate random lines in background */
for( $i=0; $i<($width*$height)/150; $i++ ) {
imageline($image, mt_rand(0,$width), mt_rand(0,$height), mt_rand(0,$width), mt_rand(0,$height), $noise_color);
}
/* create textbox and add text */
$textbox = imagettfbbox($font_size, 0, $this->font, $code) or die('Error in imagettfbbox function');
$x = ($width - $textbox[4])/2;
$y = ($height - $textbox[5])/2;
imagettftext($image, $font_size, 0, $x, $y, $text_color, $this->font , $code) or die('Error in imagettftext function');
/* output captcha image to browser */
header('Content-Type: image/jpeg');
imagejpeg($image);
imagedestroy($image);
$_SESSION['security_code'] = $code;
}

}

$width = isset($_GET['width']) ? $_GET['width'] : '120';
$height = isset($_GET['height']) ? $_GET['height'] : '40';
$characters = isset($_GET['characters']) && $_GET['characters'] > 1 ? $_GET['characters'] : '6';

$captcha = new CaptchaSecurityImages($width,$height,$characters);

?>

Để sử dụng, hãy dán đoạn mã trên vào một file php (Ví dụ: CaptchaSecurityImages.php). Sau đó để có thể hiển thị ảnh vừa tạo lên trình duyệt, bạn cần gắn file trên vào một thẻ trong trang chứa form của mình (VD: form.php):

view plaincopy to clipboardprint?









Đoạn mã sau dấu ? là chuỗi truy vấn, sẽ truyền các giá trị width, height, characters (bề rộng, chiều cao, số ký tự trong ảnh) tới file CaptchaSecurityImages.php để xử lý.

Tìm hiểu file CaptchaSecurityImages.php

Cách thức hoạt động: Đoạn mã tạo ảnh được cấu trúc dưới dạng 1 lớp (class) CaptchaSecurityImages có hàm tạo (constructor) là CaptchaSecurityImages(). Dòng cuối cùng sẽ tạo 1 đối tượng từ lớp CaptchaSecurityImages với các thông số $width, $height, $characters và hàm tạo của lớp sẽ tự động được gọi để tạo 1 ảnh ngẫu nhiên và xuất ra trình duyệt. 3 dòng phía trên sẽ kiểm tra xem có chuỗi truy vấn trong lời gọi file hay ko, nếu ko thấy chúng sẽ gán các giá trị mặc định (120, 40, 6) cho các biến $width, $height, $characters.

Lớp CaptchaSecurityImages: bao gồm 1 biến $font và 2 hàm: generateCode()CaptchaSecurityImages().

- Biến $font: xác định đường dẫn đến font sử dụng bởi chuỗi ký tự trong ảnh.

- Hàm generateCode(): Tạo chuỗi ký tự ngẫu nhiên. Mỗi ký tự trong chuỗi cần tạo sẽ được nhặt ngẫu nhiên trong chuỗi $possible. Cách thức: hàm substr() tách 1 chuỗi có độ dài 1 (1 ký tự) từ chuỗi $possible tại vị trí ngẫu nhiên tạo bởi hàm mt_rand(). Quá trình lặp lại cho đến khi đã lấy đủ được số ký tự ngẫu nhiên cần thiết qui định bởi biến $characters.

- Hàm CaptchaSecurityImages(): Tạo ảnh chứa chuỗi ký tự ngẫu nhiên.

* $this->generateCode($characters): lời gọi phương thức (hàm) generateCode() của lớp hiện hành, hàm generateCode() sẽ trả về chuỗi ký tự ngẫu nhiên và lưu vào biến $code.
* Hàm imagecreate() tạo 1 ảnh rỗng và lưu vào biến $image.
* Hàm imagecolorallocate() định màu nền, màu text, màu nhiễu.
* Hàm imagefilledellipse()mt_rand() vẽ các chấm nhiễu ngẫu nhiên trong phạm vi ảnh. Mật độ các chấm nhiễu định bởi cận trên của biến chạy $i, ở đây lấy bằng ($width*$height)/3.
* Hàm imageline() mt_rand() vẽ các đoạn thẳng ngẫu nhiên trong phạm vi ảnh. Số lượng các đoạn thẳng định bởi cận trên của biến chạy $i, ở đây lấy bằng ($width*$height)/150.
* Hàm imagettfbbox() xác định 1 khung bao quanh chuỗi ký tự cần hiển thị. Hàm này trả về 1 mảng 8 phần tử chứa toạ độ 4 đỉnh của khung. $textbox[4], $textbox[5] lần lượt chứa toạ độ x và y của đỉnh trên bên phải của khung, kết hợp với bề rộng và chiều cao của ảnh, ta sẽ xác định được vị trí $x, $y đặt chuỗi ký tự căn giữa ảnh.
* Hàm imagettftext() vẽ chuỗi ký tự lên ảnh.
* Dùng hàm header() để nhập thêm thông tin 'Content-Type: image/jpeg' vào response header, qua đó bắt trình duyệt xử lý dữ liệu trả về từ máy chủ dưới dạng ảnh jpeg. Hàm imagejpeg() xuất ảnh ra trình duyệt và hàm imagedestroy() xoá ảnh khỏi bộ nhớ, giải phóng bộ nhớ.



Tấm ảnh đã được hoàn tất. Hàm imagettftext() là hàm quan trọng nhất, dùng để vẽ 1 chuỗi ký tự vào ảnh. Dùng hàm này, bạn có thể tăng độ khó cho tấm ảnh bằng cách điều chỉnh góc xoay, font, cỡ font, màu sắc, vị trí của từng ký tự trong chuỗi.

Tạo session: ta cần kiểm tra chuỗi mà người dùng nhập vào tại trang chứa form (form.php) có khớp với chuỗi trong ảnh hay ko, vì vậy chuỗi ngẫu nhiên vừa tạo cần được lưu vào 1 biến, và biến này phải là biến session để nó có thể dc truy cập từ trang chứa form. Biến session gọi nôm na là biến "siêu toàn bộ" (super global), nghĩa là nó vẫn tồn tại khi người dùng chuyển qua các trang khác và có thể dc truy cập từ bất cứ trang nào, để phân biệt với biến cục bộ (local) và toàn bộ (global) vốn chỉ tồn tại trong 1 trang.

- Hàm session_start(): khởi tạo 1 session mới hoặc mở session hiện hành. Sau câu lệnh này, ta có thể tạo các biến session hoặc truy cập vào các biến session đang tồn tại.

- Câu lệnh $_SESSION['security_code'] = $code; tạo 1 biến session có tên security_code (là 1 phần tử của mảng $_SESSION) và gán chuỗi ngẫu nhiên tạo ở trên cho biến này.

Download mã nguồn tại đây.
avatar
học lóm
Thành viên trung thành
Thành viên trung thành

Tổng số bài gửi : 31
Điểm : 5449
Reputation : 0
Join date : 20/05/2010

Về Đầu Trang Go down

Re: UTF-8 cho cơ sở dữ liệu MySQL

Bài gửi by học lóm on 15/6/2010, 22:14

Tạo ảnh xác thực ngẫu nhiên trong PHP

Trong bài viết này chúng ta sẽ tìm hiểu cách sử dụng thư viện GD để tại ra một hình ảnh ngẫu nhiên giúp cho việc xác thực người dùng vào website của bạn. Công việc tạo hình ảnh trong PHP được thực hiện bởi thư viện GD chứa các hàm xử lý ảnh. Để sử dụng...

Trong bài viết này chúng ta sẽ tìm hiểu cách sử dụng thư viện GD để tại ra một hình ảnh ngẫu nhiên giúp cho việc xác thực người dùng vào website của bạn.

Công việc tạo hình ảnh trong PHP được thực hiện bởi thư viện GD chứa các hàm xử lý ảnh. Để sử dụng thư viện này với PHP trên localhost trong Windows, bạn cần nạp extension php_gd2.dll bằng cách xoá dấu ";" tại dòng ;extension=php_gd2.dll trong file php.ini (từ phiên bản PHP 4.3.2 trở đi, thư viện GD1 dc thay bởi GD2). Phiên bản PHP 5 trở đi thì thư viện này tự động được kích hoạt. Để kiểm tra xem thư viện có hoạt động hay không, bạn sử dụng đoạn mã sau đây:

view plaincopy to clipboardprint?



  1. if (function_exists('imagecreate')) {
  2. echo "GD Library is enabled
    \r\n
    ";   
  3. var_dump(gd_info());
  4. echo "";
  5. } else {
  6. }
  7. ?>


if (function_exists('imagecreate')) {
echo "GD Library is enabled
\r\n
";
var_dump(gd_info());
echo "
";
} else {
}
?>



Đoạn mã này kiểm tra việc nạp hàm imagecreate() được gọi. Hàm này là một hàm nằm trong thư viện GD và sẽ được nạp và có thể truy cập được nếu như thư viện GD nạp được vào ứng dụng. Tùy vào phiên bản PHP của bạn mà thư viện này có được kích hoạt ngay hay không, bạn có thể nhận được kết quả tương tự như sau:

GD Library is enabled

array(12) {
["GD Version"]=>
string(27) "bundled (2.0.34 compatible)"
["FreeType Support"]=>
bool(true)
["FreeType Linkage"]=>
string(13) "with freetype"
["T1Lib Support"]=>
bool(true)
["GIF Read Support"]=>
bool(true)
["GIF Create Support"]=>
bool(true)
["JPG Support"]=>
bool(true)
["PNG Support"]=>
bool(true)
["WBMP Support"]=>
bool(true)
["XPM Support"]=>
bool(false)
["XBM Support"]=>
bool(true)
["JIS-mapped Japanese Font Support"]=>
bool(false)
}



Nếu không nhận được kết quả như trên, bạn cần nạp extension php_gd2.dll bằng cách xoá dấu ";" tại dòng ;extension=php_gd2.dll trong file php.ini (từ phiên bản PHP 4.3.2 trở đi, thư viện GD1 dc thay bởi GD2). Để tìm được file này bạn sử dụng đoạn mã:

  1. phpinfo();
  2. ?>

phpinfo();
?>


Bây gờ, bạn hãy thử tạo ra một hình ảnh chứa các số ngẫu nhiên, giống như trong các ứng dụng web sử dụng để thẩm tra người dùng với đoạn mã:view plaincopy to clipboardprint?




  1. session_start();
  2. // generate 4 digit random number
  3. $rndval = rand(1000, 9999);
  4. // create the hash for the random number and put it in the session
  5. $_SESSION['rndnum'] = md5($rndval);
  6. // create the image
  7. $img = imagecreate(60, 30);
  8. // set background image
  9. $bgc = imagecolorallocate ($img, 255, 251, 205);
  10. // the text color is black
  11. $fontcolor = imagecolorallocate ($img, 0, 0, 0);
  12. // write the random number
  13. imagestring ($img, 5, 5, 8, $rndval, $fontcolor);
  14. // send the content type header so the image is displayed properly
  15. header('Content-type: image/jpeg');
  16. // send the image to the browser
  17. imagejpeg($img);
  18. // destroy the image to free up the memory
  19. imagedestroy($img);
  20. ?>


session_start();
// generate 4 digit random number
$rndval = rand(1000, 9999);
// create the hash for the random number and put it in the session
$_SESSION['rndnum'] = md5($rndval);
// create the image
$img = imagecreate(60, 30);
// set background image
$bgc = imagecolorallocate ($img, 255, 251, 205);
// the text color is black
$fontcolor = imagecolorallocate ($img, 0, 0, 0);
// write the random number
imagestring ($img, 5, 5, 8, $rndval, $fontcolor);
// send the content type header so the image is displayed properly
header('Content-type: image/jpeg');
// send the image to the browser
imagejpeg($img);
// destroy the image to free up the memory
imagedestroy($img);
?>

Kết quả thu được như sau:



[HaiPhong-Aptech st]
avatar
học lóm
Thành viên trung thành
Thành viên trung thành

Tổng số bài gửi : 31
Điểm : 5449
Reputation : 0
Join date : 20/05/2010

Về Đầu Trang Go down

Re: UTF-8 cho cơ sở dữ liệu MySQL

Bài gửi by học lóm on 15/6/2010, 22:16

Thuật toán tìm kiếm chuỗi

Trong bài viết này chúng ta sẽ quan tâm đến việc tìm kiếm tất cả các vị trí xuất hiện của mẫu trên một văn bản. Cài đặt sẽ dùng một hàm ra : Output để thông báo vị trí tìm thấy mẫu. I. Mở đầu Dữ liệu trong máy tính được lưu trữ dưới rất nhiều dạng khác...

Trong bài viết này chúng ta sẽ quan tâm đến việc tìm kiếm tất cả các vị trí xuất hiện của mẫu trên một văn bản. Cài đặt sẽ dùng một hàm ra : Output để thông báo vị trí tìm thấy mẫu.
I. Mở đầu



Dữ liệu trong máy tính được lưu trữ dưới rất nhiều dạng khác nhau, nhưng sử dụng chuỗi vẫn là một trong những cách rất phổ biến. Trên chuỗi các đơn vị dữ liệu không có ý nghĩa quan trọng bằng cách sắp xếp của chúng. Ta có thể thấy các dạng khác nhau của chuỗi như ở các file dữ liệu, trên biểu diễn của các gen, hay chính văn bản chúng ta đang đọc.

Một phép toán cơ bản trên chuỗi là đối sánh mẫu (pattern matching), bài toán yêu cầu ta tìm ra một hoặc nhiều vị trí xuất hiện của mẫu trên một văn bản.. Trong đó mẫu và văn bản là các chuỗi có độ dài N và M (M ≤ N), tập các ký tự được dùng gọi là bảng chữ cái å, có số lượng là d.

Việc đối sánh mẫu diễn ra với nhiều lần thử trên các đoạn khác nhau của văn bản. Trong đó cửa sổ là một chuỗi M ký tự liên tiếp trên văn bản. Mỗi lần thử chương trình sẽ kiểm tra sự giống nhau giữa mẫu với cửa sổ hiện thời. Tùy theo kết quả kiểm tra cửa sổ sẽ được dịch đi sang phải trên văn bản cho lần thử tiếp theo.

Trong trình bày này chúng ta sẽ quan tâm đến việc tìm kiếm tất cả các vị trí xuất hiện của mẫu trên một văn bản. Cài đặt sẽ dùng một hàm ra : Output để thông báo vị trí tìm thấy mẫu.
II. Thuật toán Brute Force



Có lẽ cái tên của thuật toán này đã nói lên tất cả (brute nghĩa là xúc vật, force nghĩa là sức mạnh). Thuật toán brute force thử kiểm tra tất cả các vị trí trên văn bản từ 1 cho đến n-m+1. Sau mỗi lần thử thuật toán brute force dịch mẫu sang phải một ký tự cho đến khi kiểm tra hết văn bản.

Thuật toán brute force không cần công việc chuẩn bị cũng như các mảng phụ cho quá trình tìm kiếm. Độ phức tạp tính toán của thuật toán này là O(n*m)


function IsMatch(const X: string; m: integer;

const Y: string; p: integer): boolean;

var

i: integer;

begin

IsMatch := false;

Dec(p);

for i := 1 to m do

if X <> Y[p + i] then Exit;

IsMatch := true;

end;



procedure BF(const X: string; m: integer;

const Y: string; n: integer);

var

i: integer;

begin

for i := 1 to n - m + 1 do

if IsMatch(X, m, Y, i) then

Output(i); { Thông báo tìm thấy mẫu tại vị trí i của văn bản }

end;


III. Thuật toán Knuth-Morris-Pratt



Thuật toán Knuth-Morris-Pratt là thuật toán có độ phức tạp tuyến tính đầu tiên được phát hiện ra, nó dựa trên thuật toán brute force với ý tưởng lợi dụng lại những thông tin của lần thử trước cho lần sau. Trong thuật toán brute force vì chỉ dịch cửa sổ đi một ký tự nên có đến m-1 ký tự của cửa sổ mới là những ký tự của cửa sổ vừa xét. Trong đó có thể có rất nhiều ký tự đã được so sánh giống với mẫu và bây giờ lại nằm trên cửa sổ mới nhưng được dịch đi về vị trí so sánh với mẫu. Việc xử lý những ký tự này có thể được tính toán trước rồi lưu lại kết quả. Nhờ đó lần thử sau có thể dịch đi được nhiều hơn một ký tự, và giảm số ký tự phải so sánh lại.

Xét lần thử tại vị trí j, khi đó cửa sổ đang xét bao gồm các ký tự y[j…j+m-1] giả sử sự khác biệt đầu tiên xảy ra giữa hai ký tự xy[j+i-1].

Khi đóx[1…i]=y[j…i+j-1]=ua=x[i]¹y[i+j]=b. Với trường hợp này, dịch cửa sổ phải thỏa mãn v là phần đầu của xâu x khớp với phần đuôi của xâu u trên văn bản. Hơn nữa ký tự c ở ngay sau v trên mẫu phải khác với ký tự a. Trong những đoạn như v thoả mãn các tính chất trên ta chỉ quan tâm đến đoạn có độ dài lớn nhất.
SHAPE \* MERGEFORMAT



u


u


v


b


c


a


x


y


x


j


i+j-1

Dịch cửa sổ sao cho v phải khớp với uc ¹ a


Thuật toán Knuth-Morris-Pratt sử dụng mảng Next để lưu trữ độ dài lớn nhất của xâu v trong trường hợp xâu u=x[1…i-1]. Mảng này có thể tính trước với chi phí về thời gian là O(m) (việc tính mảng Next thực chất là một bài toán qui hoạch động một chiều).

Thuật toán Knuth-Morris-Pratt có chi phí về thời gian là O(m+n) với nhiều nhất là 2n-1 lần số lần so sánh ký tự trong quá trình tìm kiếm.

procedure preKMP(const X: string; m: integer;

var Next: array of integer);

var

i, j: integer;

begin

i := 1;

j := 0;

Next[1] := 0;

while (i <= m) do

begin

while (j > 0)and(X <> X[j]) do j := Next[j];

Inc(i);

Inc(j);

if X = X[j] then Next := Next[j] {v khớp với u và c¹a}

else Next := j;

end;

end;



procedure KMP(const X: string; m: integer;

const Y: string; n: integer);

var

i, j: integer;

Next: ^TIntArr; { TIntArr = array[0..maxM] of integer }

begin

GetMem(Next, (m + 1)*SizeOf(Integer));

preKMP(X, m, Next^);

i := 1;

j := 1;

while (j <= n) do

begin

{dịch đi nếu không khớp}

while (i > 0)and(X <> Y[j]) do i := Next^;

Inc(i);

Inc(j);

if i > m then

begin

Output(j - i + 1);

i := Next^;

end;

end;

FreeMem(Next, (m + 1)*SizeOf(Integer));

End;



IV. Thuật toán Deterministic Finite Automaton (máy automat hữu hạn)



Trong thuật toán này, quá trình tìm kiếm được đưa về một quá trình biến đổi trạng thái automat. Hệ thống automat trong thuật toán DFA sẽ được xây dựng dựa trên xâu mẫu. Mỗi trạng thái (nút) của automat lúc sẽ đại diện cho số ký tự đang khớp của mẫu với văn bản. Các ký tự của văn bản sẽ làm thay đổi các trạng thái. Và khi đạt được trạng cuối cùng có nghĩa là đã tìm được một vị trí xuất hiện ở mẫu.

Thuật toán này có phần giống thuật toán Knuth-Morris-Pratt trong việc nhảy về trạng thái trước khi gặp một ký tự không khớp, nhưng thuật toán DFA có sự đánh giá chính xác hơn vì việc xác định vị trí nhảy về dựa trên ký tự không khớp của văn bản (trong khi thuật toán KMP lùi về chỉ dựa trên vị trí không khớp).

Với xâu mẫu là GCAGAGAG ta có hệ automat sau
SHAPE \* MERGEFORMAT

0

2

1

3

4

5

6

7

8



G


G


G


G


G


C


C


C


G


C


A


G


A


G


A


G



Với ví dụ ở hình trên ta có:

  • Nếu đang ở trạng thái 2 gặp ký tự A trên văn bản sẽ chuyển sang trạng thái 3
  • Nếu đang ở trạng thái 6 gặp ký tự C trên văn bản sẽ chuyển sang trạng thái 2
  • Trạng thái 8 là trạng thái cuối cùng, nếu đạt được trạng thái này có nghĩa là đã tìm thất một xuất hiện của mẫu trên văn bản
  • Trạng thái 0 là trạng thái mặc định(các liên kết không được biểu thị đều chỉ về trạng thái này), ví dụ ở nút 5 nếu gặp bất kỳ ký tự nào khác G thì đều chuyển về trạng thái 0


Việc xây dựng hệ automat khá đơn giản khi được cài đặt trên ma trận kề. Khi đó thuật toán có thời gian xử lý là O(n) và thời gian và bộ nhớ để tạo ra hệ automat là O(m*d) (tùy cách cài đặt)

Nhưng ta nhận thấy rằng trong DFA chỉ có nhiều nhất m cung thuật và m cung nghịch, vì vậy việc lưu trữ các cung không cần thiết phải lưu trên ma trận kề mà có thể dùng cấu trúc danh sách kề Forward Star để lưu trữ. Như vậy thời gian chuẩn bị và lượng bộ nhớ chỉ là O(m). Tuy nhiên thời gian tìm kiếm có thể tăng lên một chút so với cách lưu ma trận kề.

Cài đặt dưới đây xin được dùng cách đơn giản(ma trận kề)


type

TAut = array[0..maxM, 0..maxd] of integer;



procedure preAUT(const X: string; m: integer; var G: TAut);

var

i, j, prefix, cur, c, newState: integer;

begin

FillChar(G, SizeOf(G), 0);

cur := 0;

for i := 1 to m do

begin

prefix := G[cur, Ord(X)]; {x[1..prefix]=x[i-prefix+1..i]}

newState := i;

G[cur, Ord(X)] := newState;

for c := 0 to maxd do {copy prefix -> newState }

G[newState, c] := G[prefix, c];

cur := newState;

end;

end;



procedure AUT(const X: string; m: integer;

const Y: string; n: integer);

var

G: ^TAut;

state, i: integer;

begin

New(G);

preAUT(X, m, G^);

state := 0;

for i := 1 to n do

begin

state := G^[state, Ord(Y)]; {chuyển trạng thái}

if state = m then Output(i - m + 1);

end;

Dispose(G);

end;


IV. Thuật toán Boyer-Moore



Thuật toán Boyer Moore là thuật toán có tìm kiếm chuỗi rất có hiệu quả trong thực tiễn, các dạng khác nhau của thuật toán này thường được cài đặt trong các chương trình soạn thảo văn bản.

Khác với thuật toán Knuth-Morris-Pratt (KMP), thuật toán Boyer-Moore kiểm tra các ký tự của mẫu từ phải sang trái và khi phát hiện sự khác nhau đầu tiên thuật toán sẽ tiến hành dịch cửa sổ đi Trong thuật toán này có hai cách dịch của sổ:

Cách thứ 1: gần giống như cách dịch trong thuật toán KMP, dịch sao cho những phần đã so sánh trong lần trước khớp với những phần giống nó trong lần sau.

Trong lần thử tại vị trí j, khi so sánh đến ký tự i trên mẫu thì phát hiện ra sự khác nhau, lúc đó x[i+1…m]=y[i+j...j+m-1]=ua=x¹y[i+j-1]=b khi đó thuật toán sẽ dịch cửa sổ sao cho đoạn u=y[i+j…j+m-1] giống với một đoạn mới trên mẫu (trong các phép dịch ta chọn phép dịch nhỏ nhất)
SHAPE \* MERGEFORMAT



u


b


c


a


x


y


x


u


dịch


u

Dịch sao cho u xuất hiện lại và c ¹ a


Nếu không có một đoạn nguyên vẹn của u xuất hiện lại trong x, ta sẽ chọn sao cho phần đôi dài nhất của u xuất hiện trở lại ở đầu mẫu.

SHAPE \* MERGEFORMAT



u


b


a


y


x


dịch


u


u


x

Dịch để một phần đôi của u xuất hiện lại trên x


Cách thứ 2: Coi ký tự đầu tiên không khớp trên văn bản là b=y[i+j-1] ta sẽ dịch sao cho có một ký tự giống b trên xâu mẫu khớp vào vị trí đó (nếu có nhiều vị trí xuất hiện b trên xâu mẫu ta chọn vị trí phải nhất)

SHAPE \* MERGEFORMAT



u


b


a


y


x


dịch


u


b


x


không chứa b

Dịch để ký tự b ăn khớp với văn bản.


Nếu không có ký tự b nào xuất hiện trên mẫu ta sẽ dịch cửa sổ sao cho ký tự trái nhất của cửa sổ vào vị trí ngay sau ký tự y[i+j-1]=b để đảm bảo sự ăn khớp
SHAPE \* MERGEFORMAT



u


b


a


y


x


dịch


u


x


không chứa b

Dịch khi b không xuất hiện trong x


Trong hai cách dịch thuật toán sẽ chọn cách dịch có lợi nhất.

Trong cài đặt ta dùng mảng bmGs để lưu cách dịch 1, mảng bmBc để lưu phép dịch thứ 2(ký tự không khớp). Việc tính toán mảng bmBc thực sự không có gì nhiều để bàn. Nhưng việc tính trước mảng bmGs khá phức tạp, ta không tính trực tiếp mảng này mà tính gián tiếp thông qua mảng suff. Có suff=max{k | x[i-k+1…i]=x[m-k+1…m]}

Các mảng bmGsbmBc có thể được tính toán trước trong thời gian tỉ lệ với O(m+d). Thời gian tìm kiếm (độ phức tạp tính toán) của thuật toán Boyer-Moore là O(m*n). Tuy nhiên với những bản chữ cái lớn thuật toán thực hiện rất nhanh. Trong trường hợp tốt chi phí thuật toán có thể xuống đến O(n/m) là chi phí thấp nhất của các thuật toán tìm kiếm hiện đại có thể đạt được.

procedure preBmBc(const X: string; m: integer;

var bmBc: array of integer);

var

i: integer;

begin

for i := 0 to maxd - 1 do bmBc := m;

for i := 1 to m - 1 do bmBc[Ord(X)] := m - i;

end;



procedure suffixes(const X: string; m: integer;

var suff: array of integer);

var

right, left, i: integer;

begin

suff[m] := m;

left := m;

for i := m - 1 downto 1 do

if (i > left)and(suff[i + m - right] < i - left) then

suff := suff[i + m - right]

else

begin

if (i < left) then left := i;

right := i;

while (left >= 1)and(X = X[left + m - right]) do

Dec(left);

suff := right - left; {X[left…right] = X[m+left-right…m]}

end;

end;



procedure preBmGs(const X: string; m: integer;

var bmGs: array of integer);

var

i, j: integer;

suff: ^TIntArr;

begin

GetMem(suff, (m + 1)*SizeOf(Integer));

suffixes(X, m, suff^); {Tính mảng suff}

for i := 1 to m do bmGs := m;

j := 0;

for i := m downto 0 do

if (i = 0)or(suff^ = i) then

while (j < m - i) do

begin

{Nếu bmGs[j] chưa có giá trị thì điền vào}

if bmGs[j] = m then bmGs[j] := m - i;

Inc(j);

end;

for i := 1 to m - 1 do bmGs[m - suff^] := m - i; {đảo lại}

FreeMem(suff, (m + 1)*SizeOf(Integer));

end;



procedure BM(const X: string; m: integer;

const Y: string; n: integer);

var

i, j: integer;

bmBc, bmGs: ^TIntArr;

begin

GetMem(bmBc, (m + 1)*SizeOf(Integer));

GetMem(bmGs, (m + 1)*SizeOf(Integer));



preBmBc(X, m, bmBc^);

preBmGs(X, m, bmGs^);

j := 1;

while (j <= n - m + 1) do

begin

i := m;

while (i >= 1)and(X = Y[i + j - 1]) do Dec(i);

if (i < 1) then

begin

Output(j);

j := j + bmGs^[1];

end

else {chọn cách dịch được lợi nhất }

j := j + Max(bmGs^, bmBc^[Ord(Y[i + j - 1])] - m + i);

end;

FreeMem(bmBc, (m + 1)*SizeOf(Integer));

FreeMem(bmGs, (m + 1)*SizeOf(Integer));

end;



Thuật toán Boyer-Moore có thể đạt tới chi phí O(n/m) là nhờ có cách dịch thứ 2 “ký tự không khớp”. Cách chuyển cửa sổ khi gặp “ký tự không khớp” cài đặt vừa đơn giản lại rất hiệu quả trong các bảng chữ cái lớn nên có nhiều thuật toán khác cũng đã lợi dụng các quét mẫu từ phải sang trái để sử dụng cách dịch này.

Tuy nhiên chi phí thuật toán của Boyer-Moore là O(m*n) vì cách dịch thứ nhất của thuật toán này không phân tích triệt để các thông tin của những lần thử trước, những đoạn đã so sánh rồi vẫn có thể bị so sánh lại. Có một vài thuật toán đã cải tiến cách dịch này để đưa đến chi phí tính toán của thuật toán Boyer-Moore là tuyến tính. (xin tham khảo thêm trong chương trinh demo đi kèm)
VII. Thuật toán Karp-Rabin



Karp-Rabin bài toán tìm kiếm chuỗi không khác nhiều so với bài toán tìm kiếm chuẩn. Tại đây một hàm băm được dùng để tránh đi sự so sánh không cần thiết. Thay vì phải so sánh tất các vị trí của văn bản, ta chỉ cần so sánh những cửa sổ bao gồm những ký tự “có vẻ giống” mẫu.

Trong thuật toán này hàm băm phải thỏa mãn một số tính chất như phải dễ dàng tính được trên chuỗi, và đặc biệt công việc tính lại phải đơn giản để ít ảnh hưởng đến thời gian thực hiện của thuật toán. Và hàm băm được chọn ở đây là:
hash(w[i…i+m-1]) = h = (w*dm-1 + w[i+1]*dm-2 + … w[i+m-1]*d0) mod q


Việc tính lại hàm băm sau khi dịch cửa sổ đi một ký tự chỉ đơn gian như sau:
h = ((h – w[i]*dm-1)*d + w[i+m]


Trong bài toán này ta có thể chọn d = 2 để tiện cho việc tính toán a*2 tương đương a shl 1. Và không chỉ thế ta chọn q = MaxLongint khi đó phép mod q không cần thiết phải thực hiện vì sự tràn số trong tính toán chính là một phép mod có tốc độ rất nhanh.

Việc chuẩn bị trong thuật toán Karp-Rabin có độ phức tạp O(m). Tuy vậy thời gian tìm kiếm lại tỉ lệ với O(m*n) vì có thể có nhiều trường hợp hàm băm của chúng ta bị lừa và không phát huy tác dụng. Nhưng đó chỉ là những trường hợp đặc biệt, thời gian tính toán của thuật toán KR trong thực tế thường tỉ lệ với O(n+m). Hơn nữa thuật toán KR có thể dễ dàng mở rộng cho các mẫu, văn bản dạng 2 chiều, do đó khiến cho nó trở nên hữu ích hơn so với các thuật toán còn lại trong việc xử lý ảnh.

procedure KR(const X: string; m: integer;

const Y: string; n: integer);

var

dM, hx, hy: longint;

i, j: integer;

begin

{$Q-} { Disable arithmetic overflow checking }

dM := 1;

for i := 1 to m - 1 do dM := dM shl 1;

hx := 0;

hy := 0;

for i := 1 to m do

begin

hx := (hx shl 1) + Ord(X);

hy := (hy shl 1) + Ord(Y);

end;

j := 1;

while j <= n - m do

begin

if hx = hy then

if IsMatch(X, m, Y, j) then Output(j);

{hàm IsMatch trong phần BruteForce}

hy := ((hy - Ord(Y[j])*dM) shl 1) + Ord(Y[j + m]); {Rehash}

Inc(j);

end;

if hx = hy then

if IsMatch(X, m, Y, j) then Output(j);

end;


VIII. Các thuật toán khác



Một số thuật toán nêu trên chưa phải là tất cả các thuật toán tìm kiếm chuỗi hiện có. Nhưng chúng đã đại diện cho đa số các tư tưởng dùng để giải bài toán tìm kiếm chuỗi.

Các thuật toán so sánh mẫu lần lượt từ trái sang phải thường là các dạng cải tiến (và cải lùi) của thuật toán Knuth-Morris-Pratt và thuật toán sử dụng Automat như: Forward Dawg Matching, Apostolico-Crochemore, Not So Naive, …

Các thuật toán so sánh mẫu từ phải sang trái đều là các dạng của thuật toán Boyer-Moore. Phải nói lại rằng thuật toán BM là thuật toán tìm kiếm rất hiệu quả trên thực tế nhưng độ phức tạp tính toán lý thuyết lại là O(m*n). Chính vì vậy những cải tiến của thuật toán này cho độ phức tạp tính toán lý thuyết tốt như: thuật toán Apostolico-Giancarlo đánh dấu lại những ký tự đã so sánh rồi để khỏi bị so sánh lặp lại, thuật toán Turbo-BM đánh giá chặt chẽ hơn các thông tin trước để có thể dịch được xa hơn và ít bị lặp, … Còn có một số cải tiến khác của thuật toán BM không làm giảm độ phức tạp lý thuyết mà dựa trên kinh nghiệm để có tốc độ tìm kiếm nhanh hơn trong thực tế. Ngoài ra, một số thuật toán kết hợp quá trình tìm kiếm của BM vào hệ thống Automat mong đạt kết quả tốt hơn.


Các thuật toán so sánh mẫu theo thứ tự đặc biệt

  • Thuật toán Galil-Seiferas và Crochemore-Perrin chúng chia mẫu thành hai đoạn, đầu tiên kiểm tra đoạn ở bên phải rồi mới kiểm tra đoạn bên trái với chiều từ trái sang phải.
  • Thuật toán Colussi và Galil-Giancarlo lại chia mẫu thành hai tập và tiến hành tìm kiếm trên mỗi tập với một chiều khác nhau.
  • Thuật toán Optimal Mismatch và Maximal Shift sắp xếp thứ tự mẫu dựa vào mật độ của ký tự và khoảng dịch được.
  • Thuật toán Skip Search, KMP Skip Search và Alpha Skip Search dựa sự phân bố các ký tự để quyết đinh vị trí bắt đầu của mẫu trên văn bản.

Các thuật toán so sánh mẫu theo thứ tự bất kỳ những thuật toán này có thể tiến hành so sánh mẫu với cửa sổ theo một thứ thự ngẫu nhiên. Những thuật toán này đều có cài đặt rất đơn giản và thường sử dụng chiêu ký tự không khớp của thuật toán Boyer-Moore. Có lẽ loại thuật toán này dựa trên ý tưởng càng so sánh loạn càng khó kiếm test chết

[HaiPhong-Aptech st]
avatar
học lóm
Thành viên trung thành
Thành viên trung thành

Tổng số bài gửi : 31
Điểm : 5449
Reputation : 0
Join date : 20/05/2010

Về Đầu Trang Go down

Re: UTF-8 cho cơ sở dữ liệu MySQL

Bài gửi by học lóm on 15/6/2010, 22:17

Cách tạo menu đa cấp trong PHP

Bài viết này hướng dẫn cho bạn cách để làm một forum nhiều children forum hay cây thư mục đa cấp bằng phương pháp đệ quy category sử dụng PHP & MySQL. Cách viết cũng rất đơn giản là chúng ta se sử dụng một function gọi lại chính nó. Vi dụ đơn giản...

Bài viết này hướng dẫn cho bạn cách để làm một forum nhiều children forum hay cây thư mục đa cấp bằng phương pháp đệ quy category sử dụng PHP & MySQL. Cách viết cũng rất đơn giản là chúng ta se sử dụng một function gọi lại chính nó. Vi dụ đơn giản chỉ với 100 lần gọi lại như sau:view plaincopy to clipboardprint?



  1. function category($x=”0″,$text=”–”){
  2. for($x=1;$x<=100;$x++) // sau mỗi lần lặp lại nâng biến $x lên một giá trị
  3. {
  4. echo $x.$text.”
    ”;
  5. category($x,$text.”–”); // function category được gọi lại
  6. }
  7. }

function category($x=”0″,$text=”–”){
for($x=1;$x<=100;$x++) // sau mỗi lần lặp lại nâng biến $x lên một giá trị
{
echo $x.$text.”
”;
category($x,$text.”–”); // function category được gọi lại
}
}

Bây giờ ta ứng dụng phương pháp đệ qui để tạo menu đa cấp như sau:
Bước 1: Run sql tạo bảng trong CSDL:

view plaincopy to clipboardprint?



  1. CREATE TABLE `multi_category` (
  2. `category_id` smallint(5) unsigned NOT NULL auto_increment,
  3. `parent_id` smallint(5) unsigned NOT NULL default ‘0′,
  4. `name` varchar(100) NOT NULL default ”,
  5. `link` varchar(100) NOT NULL default ”,
  6. `date` date NOT NULL default ‘0000-00-00′,
  7. PRIMARY KEY (`category_id`)
  8. ) TYPE=MyISAM AUTO_INCREMENT=66 ;

CREATE TABLE `multi_category` (
`category_id` smallint(5) unsigned NOT NULL auto_increment,
`parent_id` smallint(5) unsigned NOT NULL default ‘0′,
`name` varchar(100) NOT NULL default ”,
`link` varchar(100) NOT NULL default ”,
`date` date NOT NULL default ‘0000-00-00′,
PRIMARY KEY (`category_id`)
) TYPE=MyISAM AUTO_INCREMENT=66 ;

Bước 2: Tạo một file config.php



  1. $dbhost=”localhost”;
  2. $dbname=”multi_category”;
  3. $dbuser=”root”;
  4. $dbpass=”";
  5. $table=”multi_category”;
  6. $date=date(”YmdHis”);
  7. $db=mysql_connect(”$dbhost”,”$dbuser”,”$dbpass”) or die(”Die connect: “.mysql_error());
  8. mysql_select_db(”$dbname”) or die(”Die select database: “.mysql_error());
  9. ?>

$dbhost=”localhost”;
$dbname=”multi_category”;
$dbuser=”root”;
$dbpass=”";
$table=”multi_category”;
$date=date(”YmdHis”);
$db=mysql_connect(”$dbhost”,”$dbuser”,”$dbpass”) or die(”Die connect: “.mysql_error());
mysql_select_db(”$dbname”) or die(”Die select database: “.mysql_error());
?>

Bước 3: Tạo một file index.php

view plaincopy to clipboardprint?



  1. include “config.php”;
  2. ?>


  3. Multi Category







  4. Bước 4: Tạo file add_category.php[code]
  5. function show_categories($parent_id=”0″, $insert_text=”–”)
  6. {
  7. global $db;
  8. if (! $categories = mysql_query(”SELECT * FROM multi_category WHERE parent_id=”.$parent_id.” ORDER BY parent_id”, $db))
  9. {
  10. die (”cannot query”);
  11. }
  12. while ($category=mysql_fetch_array($categories, MYSQL_ASSOC))
  13. {
  14. echo(””);
  15. show_categories($category["category_id"],$insert_text.”–”);
  16. }
  17. return true;
  18. }
  19. function selectCtrl ($name, $class)
  20. {
  21. global $db;
  22. print “”;
  23. }
  24. ?>
  25. echo “




















  26. ”;
  27. echo “




  28. Multi category
    Lang type:

  29. Off
  30. Telex
  31. VNI
  32. VIQR

  33. Name:
  34. Add link to name:
    Parent Category: ”;
  35. selectCtrl(’parent’, ‘forFormDim’);
  36. print”

  37. ”;
  38. ?>

include “config.php”;
?>


Multi Category







Bước 4: Tạo file add_category.php[code]function show_categories($parent_id=”0″, $insert_text=”–”)
{
global $db;
if (! $categories = mysql_query(”SELECT * FROM multi_category WHERE parent_id=”.$parent_id.” ORDER BY parent_id”, $db))
{
die (”cannot query”);
}
while ($category=mysql_fetch_array($categories, MYSQL_ASSOC))
{
echo(””);
show_categories($category["category_id"],$insert_text.”–”);
}
return true;
}
function selectCtrl ($name, $class)
{
global $db;
print “”;
}
?>
echo “




















”;
echo “



Multi category
Lang type:

Off
Telex
VNI
VIQR

Name:
Add link to name:
Parent Category:”;
selectCtrl(’parent’, ‘forFormDim’);
print”
”;
?>

Bước 5: Tạo file add_category_action.php

view plaincopy to clipboardprint?



  1. include “config.php”;
  2. $name = $HTTP_POST_VARS['name'];
  3. $parent = $HTTP_POST_VARS['parent'];
  4. $link = $HTTP_POST_VARS['link'];
  5. $date = date (”d-m-Y”);//$HTTP_POST_VARS['date'];
  6. $query=”insert into $table (name, parent_id, link, date) values (’$name’, ‘$parent’, ‘$link’, ‘$date’)”;
  7. $result= mysql_query($query) or die(”Die query: “.mysql_error());
  8. //$n= mysql_fetch_array($result);
  9. header(”Location: index.php”);
  10. ?>

include “config.php”;
$name = $HTTP_POST_VARS['name'];
$parent = $HTTP_POST_VARS['parent'];
$link = $HTTP_POST_VARS['link'];
$date = date (”d-m-Y”);//$HTTP_POST_VARS['date'];
$query=”insert into $table (name, parent_id, link, date) values (’$name’, ‘$parent’, ‘$link’, ‘$date’)”;
$result= mysql_query($query) or die(”Die query: “.mysql_error());
//$n= mysql_fetch_array($result);
header(”Location: index.php”);
?>

Sau khi tạo đủ các file trên bạn có thể test thử. Các bạn để ý file add_category.php function đệ qui được viết trong đó. Ở đây chúng ta chỉ cần sử dụng một table sql với hai cột field đủ để thể hiện multi category, có thể dùng cái này cho forum hoặc menu nhiều cấp..vv…

(thegioiwebsite.net)


[HaiPhong-Aptech st]
avatar
học lóm
Thành viên trung thành
Thành viên trung thành

Tổng số bài gửi : 31
Điểm : 5449
Reputation : 0
Join date : 20/05/2010

Về Đầu Trang Go down

Re: UTF-8 cho cơ sở dữ liệu MySQL

Bài gửi by học lóm on 15/6/2010, 22:18

Cách phân trang trong PHP


Phân trang là một kỹ thuật luôn được sử dụng trong đa số các website thương mại điện tử. Đây là một hàm phân trang chia thành từng đoạn viết bằng PHP rất hữu ích cho các bạn có nhu cầu sử dụng:
Phân trang là một kỹ thuật luôn được sử dụng trong đa số các website thương mại điện tử. Đây là một hàm phân trang chia thành từng đoạn viết bằng PHP rất hữu ích cho các bạn có nhu cầu sử dụng: view plaincopy to clipboardprint?



  1. function divPage($total = 0,$currentPage = 0,$div = 5,$rows = 10){
  2. if(!$total || !$rows || !$div || $total<=$rows) return false;
  3. $nPage = floor($total/$rows) + (($total%$rows)?1:0);
  4. $nDiv = floor($nPage/$div) + (($nPage%$div)?1:0);
  5. $currentDiv = floor($currentPage/$div) ;
  6. $sPage = '';
  7. if($currentDiv) {
  8. $sPage .= '<< ';
  9. $sPage .= '< ';
  10. }
  11. $count =($nPage<=($currentDiv+1)*$div)?($nPage-$currentDiv*$div):$div;
  12. for($i=0;$i<$count;$i++){
  13. $page = ($currentDiv*$div + $i);
  14. $sPage .= ''.($page+1).' ';
  15. }
  16. if($currentDiv < $nDiv - 1){

  17. $sPage .= '> ';
  18. $sPage .= '>>';
  19. }

  20. ?>

function divPage($total = 0,$currentPage = 0,$div = 5,$rows = 10){
if(!$total || !$rows || !$div || $total<=$rows) return false;
$nPage = floor($total/$rows) + (($total%$rows)?1:0);
$nDiv = floor($nPage/$div) + (($nPage%$div)?1:0);
$currentDiv = floor($currentPage/$div) ;
$sPage = '';
if($currentDiv) {
$sPage .= '<< ';
$sPage .= '< ';
}
$count =($nPage<=($currentDiv+1)*$div)?($nPage-$currentDiv*$div):$div;
for($i=0;$i<$count;$i++){
$page = ($currentDiv*$div + $i);
$sPage .= ''.($page+1).' ';
}
if($currentDiv < $nDiv - 1){

$sPage .= '> ';
$sPage .= '>>';
}

?>

Giải thích các thông số:
$total: tổng số mẫu tin
$currentPage: trang hiện hành
$div: số trang trong 1 đoạn
$rows: số dòng trên 1 trang
Cách dùng hàm này như sau:view plaincopy to clipboardprint?



  1. $p = $_GET['p'];// currentPage
  2. $rows = 10; // số record trên mỗi trang
  3. $div = 5; // số trang trên 1 phân đoạn

  4. $sql = "SELECT COUNT(*) AS total FROM WHERE ";
  5. //fetch dữ liệu lấy giá trị của total, tổng số record với điều kiện là , ta được biến $total;

  6. //lấy dữ liệu cho trang $p
  7. $start = $p*$rows;
  8. $sql = "SELECT * FROM
  9. WHERE LIMIT $start,$rows";
  10. // hiển thị dữ liệu

  11. // in phân trang
  12. print divPage($total,$p,$div,$rows)
  13. ?>

  14. $p = $_GET['p'];// currentPage
    $rows = 10; // số record trên mỗi trang
    $div = 5; // số trang trên 1 phân đoạn

    $sql = "SELECT COUNT(*) AS total FROM
    WHERE ";
    //fetch dữ liệu lấy giá trị của total, tổng số record với điều kiện là , ta được biến $total;

    //lấy dữ liệu cho trang $p
    $start = $p*$rows;
    $sql = "SELECT * FROM
    WHERE LIMIT $start,$rows";
    // hiển thị dữ liệu

    // in phân trang
    print divPage($total,$p,$div,$rows)
    ?>



    [HaiPhong-Aptech st]
    avatar
    học lóm
    Thành viên trung thành
    Thành viên trung thành

    Tổng số bài gửi : 31
    Điểm : 5449
    Reputation : 0
    Join date : 20/05/2010

    Về Đầu Trang Go down

    Re: UTF-8 cho cơ sở dữ liệu MySQL

    Bài gửi by Sponsored content


    Sponsored content


    Về Đầu Trang Go down

    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang


     
    Permissions in this forum:
    Bạn không có quyền trả lời bài viết