PHP supports a variety of compression algorithms and popular compression libraries, like Bzip2, LZF and Rar, and for most common scenarios it provides excellent support for working with binary data. There's at least one working PHP implementation of a compression algorithm out there, proving that it's possible. PHP and any other interpreted language may prove inefficient for the task, but efficiency issues highly depend on the specifics of the implementation and the actual usage of your library, for which you don't provide enough information.
I would advise you to not try and create your own compression algorithm and use an established library instead, there's no point in reinventing the wheel. You don't have to use PHP if you don't want to, every web oriented language out there has support for popular compression libraries. You can use perl's Gzip and Zlib core modules, or Python's gzip or bzip2 modules. I don't know what kind of support for compression Ruby has, but this StackOverflow question can help you, if you choose Ruby.
But if for any reason you really want to write your own original compression algorithm, you should probably choose C. C is extremely portable* and if you manage to actually built a compression library then you can use it from PHP via an extension or in Python via a module. Both PHP extensions and Python modules are also commonly written in C, and it would be fairly easy to write one of those if you coped with writing a compression algorithm. And there's always the old school option of C web programming via CGI, if you don't mind diving into a world of hurt.
* There are C compilers for almost every imaginable platform and ways to use C libraries from almost every other language.