Lưu trữ

Archive for the ‘Programming’ Category

Digital Fountain Code

Tháng Một 20, 2014 1 Bình luận

Muốn di chuyển một vật thể lớn, ta có thể tháo rời các bộ phận, di chuyển đến vị trí muốn dời đến, sau đó lắp ráp lại. Trong kỹ thuật truyền thông số truyền thống cũng vậy, cơ chế để truyền một tập tin là như sau: Trước hết tập tin được chia thành các gói tin (packet) nhỏ, sau đó từng gói tin được truyền đến địa chỉ nhận. Việc truyền tin hoàn thành nếu tất cả các gói tin được truyền đến địa chỉ nhận, và kết quả phải được phản hồi lại nơi truyền để gửi lại gói tin, nếu bị thất lạc.

Hãy xét trường hợp một máy chủ phân phối dữ liệu đến nhiều nguồn nhận. Sử dụng phương pháp truyền thống thì máy chủ cần duy trì kênh truyền hai chiều với các máy trạm, và phải duy trì danh sách thông tin máy trạm nào đã nhận các gói tin nào,… Việc này rất phức tạp và tốn kém, đặc biệt trên các kênh truyền nhiều nhiễu và dễ thất lạc gói tin. Chẳng hạn như việc điều khiển tàu thăm dò trên Sao Hỏa, mỗi tín hiệu được truyền (bằng tốc độ ánh sáng) ít nhất phải hơn 10 phút sau mới có thể đến được nơi nhận, do đó việc chờ đợi phản hồi để có thể gửi lại gói tin bị mất là không hiệu quả.

Ý tưởng giải pháp

image001

Trong mã vòi phun Digital Fountain (DF), giống như việc hứng các giọt nước từ một vòi phun, các gói tin có vai trò bình đẳng như nhau, và bộ thu nhận thu được càng nhiều “giọt” càng tốt. Sau đó, với một số lượng đủ lớn các gói (giọt) tin nhận được, có thể ráp lại thành dữ liệu cần truyền. Đặc điểm đó cũng là nguồn gốc cho tên gọi Vòi phun số: cốc nước sẽ đầy nếu nhận được nhiều giọt nước và không có sự phân biệt giữa các giọt.

Việc mã hóa là như sau:

  • Dữ liệu được chia nhỏ thành k phần,
  • Một số (trong k phần) được chọn, các phần đó được tổ hợp lại với nhau bằng phép XOR để hình thành một “giọt” tin. Mỗi giọt tin được liên kết với danh sách gồm các phần đã chọn (danh sách này thực tế được sinh ra một cách giả ngẫu nhiên).

Việc sinh giọt tin như vậy được lặp lại cho đến khi cần thiết. Có tất cả 2k lựa chọn khác nhau, tương ứng với các giọt khác nhau. Cuối quá trình mã hóa, sẽ có n giọt được sinh ra (thông thường n > k), mỗi giọt đều chứa trong mình thông tin gốc đã được pha trộn

Minh họa bằng hình ảnh:

Dữ liệu gốc, được chia thành k = 6 phần.

image002

Một “giọt” được sinh ra bằng phép XOR giữa các phần 1, 2 và 3. Giọt khác, được sinh ra từ các phần 1, 5 và 6:

image003

Giải mã:

Việc giải mã cũng giống như giải một hệ phương trình với k ẩn số (phần dữ liệu), trong đó mỗi “giọt” tin đóng vai trò một phương trình trong hệ. Như vậy, nói chung cần ít nhất k phương trình để giải.

image006

Trên thực tế, nếu chỉ với k giọt, trong hầu hết trường hợp thì xác suất để giải mã thành công chỉ là 30%. Để tăng xác suất giải mã, cần tăng số lượng giọt tin nhận được. Số lượng các giọt thừa quá được gọi là overhead: overhead lớn thì xác suất giải mã càng cao. Chẳng hạn, để xác suất lỗi nhỏ hơn 10-6, cần thừa quá 20 giọt. Chú ý rằng overhead là độc lập với k: với 20 giọt thừa quá sẽ cho xác suất lỗi nhỏ hơn 10-6 với mọi k. Vậy k lớn thì tốt hơn.

image007

Xác suất giải mã đối với mức thừa quá overhead.

Một số ứng dụng của DF Code:

  • Đa truyền (multicast) tin cậy: Có nhiều vấn đề khi truyền dữ liệu cho một số lượng lớn đích đến, như hàng loạt phản hồi về các gói gửi lỗi, không đồng nhất về thời gian bắt đầu truyền nhận, … DF Code giải quyết được các vấn đề trên: Mỗi người nhận sẽ nhận những gói họ có thể nhận, và dừng lại khi họ có đủ thông tin cần thiết.
  • Download song song: Có thể tổng hợp dữ liệu từ nhiều nguồn phát DF rời nhau để được dữ liệu cần lấy, chẳng hạn trong các mạng ngang hàng BitTorrent.
  • Truyền dữ liệu khoảng cách lớn: Tăng tốc độ truyền do không cần quan tâm đến phản hồi về các gói thất lạc.
  • Máy chủ web: Khi có nhiều kết nối đến cùng một file trên máy chủ, cần phải có bộ nhớ và trạng thái cho từng kết nối. Do giới hạn tài nguyên máy chủ, dẫn tới giới hạn về số kết nối đồng thời. Để giải quyết việc này, có thể sử dụng một DF để sinh ra các gói cho tất cả các kết nối tới file cần chia sẻ.
  • Video streaming: Truyền hình (gần như) thời gian thực.
  • Các ứng dụng khác: Hệ thống lưu trữ (chẳng hạn DropBox), vệ tinh địa tĩnh, …

Lời kết

Bài này chỉ mang tính chất tổng hợp một số thông tin, mang tính chất giới thiệu ý tưởng (theo người soạn) thú vị của DF Code dành cho các bạn chưa biết. Bạn đọc có thể tìm hiểu về các ứng dụng cụ thể hơn cũng cài đặt của một số hệ mã DF cụ thể:  Raptor code, Luby transform codes.

Tham khảo:

http://www.codeproject.com/Articles/425456/Your-Digital-Fountain

https://sites.google.com/site/andrealvitali2/VirtualHDDdigitalfountain.pdf

http://inst.eecs.berkeley.edu/~ee121/sp08/handouts/fountain.ppt

http://www.eecs.harvard.edu/~michaelm/TALKS/INFORMS06.ppt

Advertisements

www.tudientoanhoc.net – Từ điển Toán học Anh Việt

Hiện nay trên internet đã có một vài trang web cho phép tra từ điển toán học online. Theo tôi được biết, các trang này đều sử dụng nguồn dữ liệu từ cuốn sách sau (dưới dạng file PDF):

Từ điển Toán học Anh – Việt với khoảng 17000 từ. Nhà xuất bản KH và KT In lần thứ 2 – 1976 Tập thể hiệu đính: Phan Đức Chính, Lê Minh Khanh, Nguyễn Tấn Lập, Lê Đình Thịnh, Nguyễn Công Thuý, Nguyễn Bác Văn Tiểu ban duyệt: Lê Văn Thiêm, Phan Đình Diệu, Trần Vinh Hiển, Nguyễn Cảnh Toàn, Nguyễn Đình Trí, Hoàng Tuỵ

Việc tra cứu tài liệu trên máy hoặc tra cứu bằng cách in tài liệu ra đều bất tiện. Do vậy việc cần thiết là xây dựng ứng dụng từ điển để tiện tra cứu trên máy hoặc môi trường web.

Thực tế, do việc chuyển đổi dữ liệu từ file tài liệu trên, nên các trang tra cứu từ điển hiện thời có những nhược điểm sau:

  • Từ thiếu nhiều (so với file tài liệu), chẳng hạn trang http://tudientoan.seotopten.net/ dẫn đầu trong kết quả tìm kiếm (do được SEO tốt), nhưng tôi được biết trang này hiện chỉ mới có khoảng 3200 từ (quá thiếu so với file PDF gốc)
  • Từ sai (do file gốc có nhiều sai sót chế bản),
  • Tra cứu không thuận tiện (chậm, khó tìm theo ý muốn)

Do vậy tôi đã tự mình thực hiện chuyển đổi lại dữ liệu từ file trên một cách (gần như tuyệt đối) đầy đủ, và viết một trang web tra cứu online, đó chính là http://www.tudientoanhoc.net

Cũng phải nói thêm rằng mặc dù file PDF trên có giới thiệu từ điển khoảng 17000 từ, nhưng thực ra khi chuyển đổi thành dữ liệu bảng tôi biết được chỉ có khoảng gần 15000 mục tra cứu, trong đó số đầu từ gốc ít hơn nhiều: khoảng 5300 từ, còn lại là các từ dẫn xuất. Tôi không được biết cuốn từ điển (bản in) gốc có số lượng từ như thế nào?

Việc chuyển đổi, chuẩn hóa dữ liệu là mất thời gian nhất, dựa vào một số quy tắc sắp thứ tự từ điển mà tôi đã phải xử lý chính tả bằng tay khá nhiều từ (khoảng 400 từ). Các từ này, trong một số bộ dữ liệu từ điển miễn phí (chẳng hạn của Hồ Ngọc Đức), cũng sai chính tả. Việc lập trình tôi chỉ viết đơn giản, viết từ đầu, trong thời gian ngắn, nên giao diện còn chưa bắt mắt và (có thể) chậm. Tôi sẽ hiệu chỉnh dần trong quá trình vận hành.

Mong trang web có ích phần nào cho các bạn trong quá trình tham khảo các tài liệu toán tiếng Anh. Mọi đóng góp, bình luận, yêu cầu tính năng, … các bạn có thể gửi tại blog này hoặc tới email handuc@gmail.com

Hàn Đức.

DXNTool – SourceCode Generator, and more..

Insertion Script

Khi lập trình các ứng dụng cơ sở dữ liệu, nhiều lúc chúng ta cần những tiện ích đơn giản dùng để sinh (generate) ra các mã trình một cách tự động từ cấu trúc cho trước. Đối với một bảng dữ liệu trong một hệ quản trị CSDL nào đó, có thể bạn đã và sẽ cần một tiện ích có các tính năng sau:

(1)    Generate câu lệnh tạo bảng;

(2)    Generate chuỗi insert dữ liệu của bảng đó;

(3)    Generate tài liệu về bảng (database table documentation) để lưu trữ;

(4)    Kết xuất (export) dữ liệu bảng ra file excel;

(5)    Generate Business Object class tương ứng theo cấu trúc bảng để thuận tiện cho việc viết mã trong các ứng dụng;

Các tính năng này, hoặc đã có sẵn trong các công cụ quản trị CSDL (chẳng hạn, SQL Server Management Studio), hoặc có thể có rải rác trong các tiện ích miễn phí và trả tiền (chẳng hạn, Tier Dev), hoặc có những hướng dẫn viết code để tự làm ra chúng trên các website về lập trình. Có thể kể ra một vài đường link sau:

http://www.codeproject.com/Articles/19719/Generate-Insertion-Scripts-Using-NET-2-0

http://www.codeproject.com/KB/codegen/TierGenerator.aspx

http://smartcodegenerator.codeplex.com/

Sau nhiều lần thử cài đặt các công cụ và tải các mã nguồn kèm hướng dẫn về chạy thử, tôi thấy chưa thật sự thỏa mãn. Do công cụ quá cồng kềnh cho một tính năng nhỏ, do công cụ quá cứng ngắc đầu ra (thay đổi phải sửa hardcode), do công cụ tốt thì phải trả tiền mà cũng không đủ các tính năng mình mong muốn,… tôi đã tự viết công cụ với các tính năng cho riêng mình.

Công cụ với mục tiêu là các tính năng nêu trên tôi đang viết vào những lúc rảnh và cũng không thật rốt ráo (cần đến đâu viết đến đó), và vẫn bổ sung dần dần các tính năng khác như generate toàn bộ một project mẫu với chức năng CRUD đầy đủ, đầu ra tùy biến theo template chỉnh sửa được. Chắc chắn rằng nhiều người đã tự làm cho mình các công cụ như vậy (chẳng hạn đồng nghiệp và bạn bè mà tôi biết) vì mỗi người mong muốn các tính năng khác nhau cho riêng mình.

Tôi xin được chia sẻ công cụ này (vẫn còn vài bug exception) cho bạn nào chưa tìm được công cụ nhỏ gọn, portable của riêng mình có thể tham khảo sử dụng, với các tính năng (1)-(4) và các ưu điểm:

–          Làm việc trên 3 Hệ quản trị CSDL thường gặp là MS SQL Server, Oracle, MySQL (có thể bổ sung các loại khác),

–          Có thể tùy biến template (file XSLT) để thay đổi output như mong muốn (hiện áp dụng cho tính năng (3)). Về nguyên tắc, có thể generate ra mã nguồn của một ngôn ngữ tùy ý,

–          Rất nhỏ gọn,

–          Portable (không cần cài đặt).

Bạn nào quan tâm, cần bổ sung các tiện ích khác có thể trao đổi thêm để hoàn thiện.

Download Here

Generate table documentation

Hình: Generate table documentation (có thể save as thành file .htm)

Kết xuất dữ liệu ra excel (2)

Một trong những nhu cầu cơ bản nhất của người dùng khi cần kết xuất dữ liệu ra excel là xuất một dataset ra file excel, mỗi datatable tương ứng với một sheet chứa dữ liệu. Trong ví dụ ở phần trước về kết xuất định dạng XML Spreedsheet tôi cũng đưa project mẫu đáp ứng nhu cầu kết xuất này. Một nhu cầu khác cũng thường gặp trong các ứng dụng nghiệp vụ, đó là điền dữ liệu vào một template có sẵn (với định dạng có thể phức tạp).

Các thư viện nguồn mở, miễn phí được tìm hiểu sử dụng trong bài viết này đều là thư viện viết bằng .NET, nếu các bạn biết các thư viện bằng ngôn ngữ khác có thể chia sẻ tại đây.

2. Kết xuất định dạng BIFF8 (Excel 97-2003 file format)

Có hai thư viện hỗ trợ định dạng BIFF8 tôi đã thử nghiệm, khá gọn nhẹ. Đó là ExcelLibrary và NPOI.

  • ExcelLibrary:

Liên kết:

http://code.google.com/p/excellibrary/

http://www.codeproject.com/Articles/16210/Excel-Reader

Theo các tác giả (người Tung Của), thư viện này hiện đang hỗ trợ định dạng BIFF và có thể hỗ trợ .xlsx trong tương lai, nhưng nhìn vào commit changes thì có vẻ như hơn một năm nay thư viện không được sửa đổi gì cả. Vậy thì hoặc bạn nào có thể bổ sung hỗ trợ định dạng .xlsx, hoặc với xlsx thì ta tìm cái khác (như các thư viện tiếp sau tôi sẽ giới thiệu).

Sử dụng ExcelLibrary, việc kết xuất một dataset ra file excel cực kỳ thuận tiện:

ExcelLibrary.DataSetHelper.CreateWorkbook(“ExcelLibrary.xls”, ds);

Cách mở file, đọc cell, tạo workbook, duyệt sheet các bạn có thể xem trong bài báo trên Codeproject. Theo cá nhân tôi, thư viện này ưu điểm nhỏ gọn tốc độ, nhược điểm là chưa hỗ trợ về định dạng tài liệu (font, màu, …), và dường như tác giả đã quên nó.

  • NPOI

Liên kết:

http://npoi.codeplex.com/

http://code.google.com/p/npoi/

Đây là thư viện khá tốt và là ấn bản .NET của dự án trước đó viết trên nền java (http://poi.apache.org/).  Ưu điểm của NPOI (Copy-Paste):

a. It’s totally free to use

b. Cover most features of Excel (cell style, data format, formula and so on)

c. Profressionl support service (even 24*7) from NPOI team (not free)

d. Support xls, xlsx, docx.

e. Designed to be interface-oriented (take a look at NPOI.SS namespace)

f. Support not only export but also import

g. .Net 2.0 based even for xlsx and docx (though we also support .NET 4.0)

h. Successful cases from all over the world

i. huge amout of basic examples

 Một ưu điểm nữa là nó vẫn đang được phát triển. Nhược điểm là sử dụng hơi rườm rà.

Phiên bản từ 2.0 có hỗ trợ định dạng xlsx. Project mẫu tôi gửi ở đây có sử dụng phiên bản 1.2.5, trong đó tôi viết thêm lớp trung gian NPOISheet để sử dụng được dễ dàng hơn.

Phần sau: Các thư viện hỗ trợ xlsx.

Chuyên mục:Programming Thẻ:, ,

Kết xuất dữ liệu ra Excel (1)

Tháng Bảy 14, 2012 2 comments

Khi phát triển các phần mềm nghiệp vụ nói chung, sẽ có lúc bắt gặp yêu cầu kết xuất dữ liệu ra file excel để xử lý. Người dùng văn phòng rất ưa chuộng sự linh hoạt của phần mềm bảng tính phổ biến hàng đầu của Microsoft này. Các hãng thứ ba cũng thường có tính năng kết xuất dữ liệu ra một số định dạng phổ biến trong đó có excel.

Để làm được việc này, người phát triển có thể sử dụng thư viện của bộ office (Microsoft.Office.Interop.Excel.dll) để thao tác, ưu điểm là có thể tạo ra các file excel có định dạng phức tạp, nhược điểm là viết code cồng kềnh và khi triển khai cần cài đặt MS Office trên máy đích.
Tôi muốn chia sẻ ở bài này các cách khác nhau có thể kết xuất Excel mà hoàn toàn không sử dụng thư viện của Microsoft (do vậy khi deploy không yêu cầu môi trường phải cài đặt MS Office).
1. Kết xuất định dạng XML Spreadsheet

Nếu yêu cầu kết xuất excel chỉ đơn giản là đổ một datatable ra thành một sheet với các dòng dữ liệu tương ứng trong excel, thì cách sau đây là đơn giản nhất và chỉ cần sử dụng đọc ghi file text để xử lý. Ở đây tôi sử dụng C#2.0 để minh họa cho việc này.

Bước 1: Bạn tạo template, bằng cách tạo một file excel bình thường, có một sheet thể hiện dữ liệu của một bảng mẫu, nội dung và định dạng header theo ý bạn, chẳng hạn như hình vẽ.

Bước 2: Lưu file trên thành định dạng XML Spreadsheet 2003, chẳng hạn tên file là Book1.xml. Bạn có thể mở file này bằng notepad để thấy nội dung dạng xml của nó. Bây giờ bạn sẽ fill dữ liệu từ một datatable nào đó ra dạng XML spreadsheet theo template mà bạn tạo ra này. Dữ liệu các cell sẽ nằm trong cặp thẻ (“TableName” là tên của sheet)

<Worksheet ss:Name=”TableName”> </Worksheet>

Bước 3: Viết ứng dụng tạo ra file text có định dạng trên bằng cách thay các dữ liệu cell mẫu trong file Book1.xml bằng dữ liệu các cell đọc được từ Datatable.

Bạn có thể tải mã nguồn ứng dụng mẫu tôi viết tại đây, trong đó tôi sử dụng một file xml để làm dữ liệu input cho datatable, bạn có thể kết nối đến các DBMS để lấy dữ liệu theo ý muốn (để đơn giản tôi đã coi các trường dữ liệu đều là kiểu string).

Chú ý rằng định dạng XML Spreadsheet có nội dung dạng XML, không phải excel chuẩn. Ở các phần sau tôi sẽ giới thiệu các thư viện tôi đã thử nghiệm trong việc kết xuất dữ liệu ra xml, excel cấu trúc BIFF (Excel 2003 trở về trước), excel 2007 (xlsx). Hy vọng sẽ có ích cho các bạn khi tìm kiếm một giải pháp thay thế cho việc sử dụng thư viện của bộ MS Office.

Chuyên mục:Programming Thẻ:, ,